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.
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.
Item Type: | Conference item (Paper) |
---|---|
Full text: | Publisher-imposed embargo (AM) Accepted Manuscript File format - PDF (332Kb) |
Status: | Peer-reviewed |
Publisher Web site: | https://www.springer.com/gp/computer-science/lncs |
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
Export: | |
Look up in GoogleScholar |