Disjoint Paths and Connected Subgraphs for H-Free Graphs.

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

doi:10.1007/978-3-030-79987-8_29

Disjoint Paths and Connected Subgraphs for H-Free Graphs.

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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≥ 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
Title of host publication	Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings
Editors	Paola Flocchini, Lucia Moura
Publisher	Springer
Pages	414-427
Number of pages	14
ISBN (Print)	9783030799861
DOIs	https://doi.org/10.1007/978-3-030-79987-8_29
Publication status	Published - 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12757 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-030-79987-8_29

Kern2021_Chapter_DisjointPathsAndConnectedSubgrFinal published version, 367 KBLicence: Taverne

https://dblp.org/rec/conf/iwoca/KernMPSL21

Cite this

Kern, W., Martin, B., Paulusma, D., Smith, S., & Leeuwen, E. J. V. (2021). Disjoint Paths and Connected Subgraphs for H-Free Graphs. In P. Flocchini, & L. Moura (Eds.), Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings (pp. 414-427). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12757 LNCS). Springer. https://doi.org/10.1007/978-3-030-79987-8_29

Kern, Walter ; Martin, Barnaby ; Paulusma, Daniël et al. / Disjoint Paths and Connected Subgraphs for H-Free Graphs. Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings. editor / Paola Flocchini ; Lucia Moura. Springer, 2021. pp. 414-427 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{004161f1b6254963b0df556517c02bfa,

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≥ 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.",

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

note = "Funding Information: D. Paulusma?Supported by the Leverhulme Trust (RPG-2016-258). Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.",

year = "2021",

doi = "10.1007/978-3-030-79987-8_29",

language = "English",

isbn = "9783030799861",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "414--427",

editor = "Paola Flocchini and Lucia Moura",

booktitle = "Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings",

}

Kern, W, Martin, B, Paulusma, D, Smith, S & Leeuwen, EJV 2021, Disjoint Paths and Connected Subgraphs for H-Free Graphs. in P Flocchini & L Moura (eds), Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12757 LNCS, Springer, pp. 414-427. https://doi.org/10.1007/978-3-030-79987-8_29

Disjoint Paths and Connected Subgraphs for H-Free Graphs. / Kern, Walter; Martin, Barnaby; Paulusma, Daniël et al.
Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings. ed. / Paola Flocchini; Lucia Moura. Springer, 2021. p. 414-427 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12757 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Kern, Walter

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

AU - Leeuwen, Erik Jan van

PY - 2021

Y1 - 2021

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≥ 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≥ 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.

UR - http://www.scopus.com/inward/record.url?scp=85111953680&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-79987-8_29

DO - 10.1007/978-3-030-79987-8_29

M3 - Conference contribution

SN - 9783030799861

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 414

EP - 427

BT - Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings

A2 - Flocchini, Paola

A2 - Moura, Lucia

PB - Springer

ER -

Kern W, Martin B, Paulusma D, Smith S, Leeuwen EJV. Disjoint Paths and Connected Subgraphs for H-Free Graphs. In Flocchini P, Moura L, editors, Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings. Springer. 2021. p. 414-427. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-79987-8_29

Disjoint Paths and Connected Subgraphs for H-Free Graphs.

Abstract

Publication series

Access to Document

Fingerprint

Cite this