Disjoint Paths and Connected Subgraphs for H-Free Graphs

Walter Kern; Barnaby Martin; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen

doi:10.48550/arXiv.2105.06349

Disjoint Paths and Connected Subgraphs for H-Free Graphs

Walter Kern
, Barnaby Martin
, Daniël Paulusma
, Siani Smith
, Erik Jan van Leeuwen

Mathematics of Operations Research

Research output: Working paper › Preprint › Academic

10 Downloads (Pure)

Abstract

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for $H$-free graphs. If $k$ is fixed, we obtain the $k$-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every $k \geq 1$. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of $k$-Disjoint Connected Subgraphs for $H$-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for $H$-free graphs as for Disjoint Paths.

Original language	English
Publisher	ArXiv.org
Number of pages	16
DOIs	https://doi.org/10.48550/arXiv.2105.06349
Publication status	Published - 13 May 2021

Keywords

math.CO
cs.CC
cs.DM
cs.DS

Access to Document

10.48550/arXiv.2105.06349

Article-v1Final published version, 415 KB

Disjoint paths and connected subgraphs for H-free graphs
Kern, W., Martin, B., Paulusma, D., Smith, S. & van Leeuwen, E. J., 4 Jan 2022, In: Theoretical computer science. 898, p. 59-68 10 p.
Research output: Contribution to journal › Article › Academic › peer-review
9 Link opens in a new tab Citations (Scopus)
Disjoint Paths and Connected Subgraphs for H-Free Graphs
Kern, W., Martin, B., Paulusma, D., Smith, S. & van Leeuwen, E. J., 2021, Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings. Flocchini, P. & Moura, L. (eds.). Cham: Springer, p. 414-427 14 p. (Lecture Notes in Computer Science; vol. 12757).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
1 Link opens in a new tab Citation (Scopus)

Cite this

@techreport{10221be7c20e4699a3b4afc9165ffc63,

title = "Disjoint Paths and Connected Subgraphs for H-Free Graphs",

abstract = "The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for \$H\$-free graphs. If \$k\$ is fixed, we obtain the \$k\$-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every \$k \textbackslash{}geq 1\$. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of \$k\$-Disjoint Connected Subgraphs for \$H\$-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for \$H\$-free graphs as for Disjoint Paths. ",

keywords = "math.CO, cs.CC, cs.DM, cs.DS",

author = "Walter Kern and Barnaby Martin and Dani{\"e}l Paulusma and Siani Smith and \{van Leeuwen\}, \{Erik Jan\}",

year = "2021",

month = may,

day = "13",

doi = "10.48550/arXiv.2105.06349",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Disjoint Paths and Connected Subgraphs for H-Free Graphs

AU - Kern, Walter

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

AU - van Leeuwen, Erik Jan

PY - 2021/5/13

Y1 - 2021/5/13

N2 - The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for $H$-free graphs. If $k$ is fixed, we obtain the $k$-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every $k \geq 1$. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of $k$-Disjoint Connected Subgraphs for $H$-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for $H$-free graphs as for Disjoint Paths.

AB - The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for $H$-free graphs. If $k$ is fixed, we obtain the $k$-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every $k \geq 1$. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of $k$-Disjoint Connected Subgraphs for $H$-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for $H$-free graphs as for Disjoint Paths.

KW - math.CO

KW - cs.CC

KW - cs.DM

KW - cs.DS

U2 - 10.48550/arXiv.2105.06349

DO - 10.48550/arXiv.2105.06349

M3 - Preprint

BT - Disjoint Paths and Connected Subgraphs for H-Free Graphs

PB - ArXiv.org

ER -

Disjoint Paths and Connected Subgraphs for H-Free Graphs

Abstract

Keywords

Access to Document

Fingerprint

Research output

Disjoint paths and connected subgraphs for H-free graphs

Disjoint Paths and Connected Subgraphs for H-Free Graphs

Cite this