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

N1 - Funding Information:
D. Paulusma?Supported by the Leverhulme Trust (RPG-2016-258).
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

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 -