We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Disjoint paths and connected subgraphs for H-free graphs

Kern, W. and Martin, B. and Paulusma, D. and Smith, S. and van Leeuwen, E.J. (2022) 'Disjoint paths and connected subgraphs for H-free graphs.', Theoretical computer science., 898 . pp. 59-68.


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.

Item Type:Article
Full text:Publisher-imposed embargo until 22 October 2022.
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
File format - PDF
Publisher Web site:
Publisher statement:© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:18 October 2021
Date deposited:25 October 2021
Date of first online publication:22 October 2021
Date first made open access:22 October 2022

Save or Share this output

Look up in GoogleScholar