Disjoint Paths and Connected Subgraphs for H-Free Graphs.
Publication date
2021
Authors
Kern, Walter
Martin, Barnaby
Paulusma, Daniël
Smith, Siani
van Leeuwen, Erik Jan
Editors
Flocchini, Paola
Moura, Lucia
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
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.
Keywords
Taverne, Theoretical Computer Science, General Computer Science
Citation
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. 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