Disjoint paths and connected subgraphs for H-free graphs

Kern, W.; Martin, B.; Paulusma, D.; Smith, S.; van Leeuwen, E.J.

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.

Citation

Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Disjoint paths and connected subgraphs for H-free graphs

• Presentation Conference Type: Conference Paper (published)
• Acceptance Date: May 1, 2021
• Online Publication Date: Jun 30, 2021
• Publication Date: 2021
• Deposit Date: May 28, 2021
• Publicly Available Date: Jun 1, 2021
• Print ISSN: 0302-9743
• Publisher: Springer Verlag
• Volume: 12757
• Pages: 414-427
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Book Title: Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings
• ISBN: 9783030799861
• DOI: https://doi.org/10.1007/978-3-030-79987-8_29
• Public URL: https://durham-repository.worktribe.com/output/1625144