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 vertex 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. Moreover, we give exact algorithms for Disjoint Paths and Disjoint Connected Subgraphs on graphs with n vertices and m edges that have running times of O(2nn 2 k) and O(3n km), respectively.

Citation

Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Disjoint paths and connected subgraphs for H-free graphs. Theoretical Computer Science, 898, 59-68. https://doi.org/10.1016/j.tcs.2021.10.019

• Journal Article Type: Article
• Acceptance Date: Oct 18, 2021
• Online Publication Date: Oct 22, 2021
• Publication Date: Jan 4, 2022
• Deposit Date: Oct 23, 2021
• Publicly Available Date: Oct 22, 2022
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 898
• Pages: 59-68
• DOI: https://doi.org/10.1016/j.tcs.2021.10.019
• Public URL: https://durham-repository.worktribe.com/output/1225786