Disjoint paths and connected subgraphs for H-free graphs

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

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)

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(2nn2k) and O(3nkm), respectively.

Original languageEnglish
Pages (from-to)59-68
Number of pages10
JournalTheoretical Computer Science
Volume898
DOIs
Publication statusPublished - 4 Jan 2022

Bibliographical note

Funding Information:
Daniël Paulusma was supported by the Leverhulme Trust (RPG-2016- 258).

Publisher Copyright:
© 2021 Elsevier B.V.

Keywords

  • Complexity dichotomy
  • Disjoint paths
  • H-free graph

Fingerprint

Dive into the research topics of 'Disjoint paths and connected subgraphs for H-free graphs'. Together they form a unique fingerprint.

Cite this