Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

Barnaby Martin; Daniël Paulusma; Siani Smith; Erik Jan van Leeuwen

doi:10.1007/s00453-023-01109-z

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

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

^*Corresponding author for this work

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

Abstract

Paths P¹, … , P^k in a graph G= (V, E) are mutually induced if any two distinct Pⁱ and P^j have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices (s_i, t_i) contains k mutually induced paths Pⁱ such that each Pⁱ starts from s_i and ends at t_i. This is a classical graph problem that is NP-complete even for k= 2. We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

Original language	English
Pages (from-to)	2580-2604
Number of pages	25
Journal	Algorithmica
Volume	85
Issue number	9
DOIs	https://doi.org/10.1007/s00453-023-01109-z
Publication status	Published - 11 Mar 2023

Bibliographical note

Funding Information:
The authors thank Paweł Rzążewski for the argument using blob graphs, which simplified two of our proofs and led to the case H = P 6 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H=P_6$$\end{document} in Theorem 1. The paper did not receive support from external funding agencies.

Publisher Copyright:
© 2023, The Author(s).

Keywords

Complexity dichotomy
Connectivity
H-free graph
Induced subgraphs

Access to Document

10.1007/s00453-023-01109-zLicence: CC BY

Handle.net

Persistent link

Cite this

@article{bdac9eb850bf449badce9f00903e0a61,

title = "Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs",

abstract = "Paths P1, … , Pk in a graph G= (V, E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices (si, ti) contains k mutually induced paths Pi such that each Pi starts from si and ends at ti. This is a classical graph problem that is NP-complete even for k= 2. We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.",

keywords = "Complexity dichotomy, Connectivity, H-free graph, Induced subgraphs",

author = "Barnaby Martin and Dani{\"e}l Paulusma and Siani Smith and \{van Leeuwen\}, \{Erik Jan\}",

note = "Funding Information: The authors thank Pawe{\l} Rz{\c a}{\.z}ewski for the argument using blob graphs, which simplified two of our proofs and led to the case H = P 6 \textbackslash{}documentclass[12pt]\{minimal\} \textbackslash{}usepackage\{amsmath\} \textbackslash{}usepackage\{wasysym\} \textbackslash{}usepackage\{amsfonts\} \textbackslash{}usepackage\{amssymb\} \textbackslash{}usepackage\{amsbsy\} \textbackslash{}usepackage\{mathrsfs\} \textbackslash{}usepackage\{upgreek\} \textbackslash{}setlength\{\textbackslash{}oddsidemargin\}\{-69pt\} \textbackslash{}begin\{document\}\$\$H=P\_6\$\$\textbackslash{}end\{document\} in Theorem 1. The paper did not receive support from external funding agencies. Publisher Copyright: {\textcopyright} 2023, The Author(s).",

year = "2023",

month = mar,

day = "11",

doi = "10.1007/s00453-023-01109-z",

language = "English",

volume = "85",

pages = "2580--2604",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer, New York, NY",

number = "9",

}

TY - JOUR

T1 - Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

AU - van Leeuwen, Erik Jan

N1 - Funding Information: The authors thank Paweł Rzążewski for the argument using blob graphs, which simplified two of our proofs and led to the case H = P 6 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H=P_6$$\end{document} in Theorem 1. The paper did not receive support from external funding agencies. Publisher Copyright: © 2023, The Author(s).

PY - 2023/3/11

Y1 - 2023/3/11

N2 - Paths P1, … , Pk in a graph G= (V, E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices (si, ti) contains k mutually induced paths Pi such that each Pi starts from si and ends at ti. This is a classical graph problem that is NP-complete even for k= 2. We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

AB - Paths P1, … , Pk in a graph G= (V, E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices (si, ti) contains k mutually induced paths Pi such that each Pi starts from si and ends at ti. This is a classical graph problem that is NP-complete even for k= 2. We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

KW - Complexity dichotomy

KW - Connectivity

KW - H-free graph

KW - Induced subgraphs

UR - https://www.scopus.com/pages/publications/85149736098

U2 - 10.1007/s00453-023-01109-z

DO - 10.1007/s00453-023-01109-z

M3 - Article (Academic Journal)

AN - SCOPUS:85149736098

SN - 0178-4617

VL - 85

SP - 2580

EP - 2604

JO - Algorithmica

JF - Algorithmica

IS - 9

ER -

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

Abstract

Bibliographical note

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this