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. (2021) 'Disjoint paths and connected subgraphs for H-free graphs.', IWOCA 2021 Online, 5-7 Jul 2021.


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.

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:01 May 2021
Date deposited:01 June 2021
Date of first online publication:2021
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar