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.
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.
| 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 (349Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1016/j.tcs.2021.10.019 |
| Publisher statement: | © 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| 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
| Export: | |
| Look up in GoogleScholar |
