Skip to main content

Research Repository

Advanced Search

Disjoint paths and connected subgraphs for H-free graphs

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

Disjoint paths and connected subgraphs for H-free graphs Thumbnail


Authors

W. Kern

E.J. van Leeuwen



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

Files





You might also like



Downloadable Citations