Disjoint Paths and Connected Subgraphs for H-Free Graphs

DOI10.1016/J.TCS.2021.10.019MaRDI QIDQ6367593arXivFDO

Authors Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Publication date 13 May 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2021.10.019

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.CCcs.DMcs.DSmath.CO

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 $kgeq1$. 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.

This page was built for publication: Disjoint Paths and Connected Subgraphs for H-Free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367593)