Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

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

doi:10.1007/978-3-031-15914-5_29

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: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

2 Citations (Scopus)

Abstract

Paths $$P^1,\ldots,P^k$$ in a graph $$G=(V,E)$$ are mutually induced if any two distinct $$P^i$$ 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^i$$ such that each $$P^i$$ 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
Title of host publication	Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers
Editors	Michael A. Bekos, Michael Kaufmann
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	398-411
Number of pages	14
ISBN (Print)	9783031159138
DOIs	https://doi.org/10.1007/978-3-031-15914-5_29
Publication status	Published - 2022
Event	48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022 - Tübingen, Germany Duration: 22 Jun 2022 → 24 Jun 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13453 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022
Country/Territory	Germany
City	Tübingen
Period	22/06/22 → 24/06/22

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

Keywords

complexity dichotomy
connectivity
H-free graph
induced subgraphs

Access to Document

10.1007/978-3-031-15914-5_29

Handle.net

Persistent link

Cite this

Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2022). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In M. A. Bekos, & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers (pp. 398-411). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13453 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-15914-5_29

Martin, Barnaby ; Paulusma, Daniël ; Smith, Siani et al. / Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers. editor / Michael A. Bekos ; Michael Kaufmann. Springer Science and Business Media Deutschland GmbH, 2022. pp. 398-411 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7b0614fb0be8400c8c070561bcb02050,

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

abstract = "Paths $$P^1,\ldots,P^k$$ in a graph $$G=(V,E)$$ are mutually induced if any two distinct $$P^i$$ 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^i$$ such that each $$P^i$$ 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.",

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 = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022 ; Conference date: 22-06-2022 Through 24-06-2022",

year = "2022",

doi = "10.1007/978-3-031-15914-5_29",

language = "English",

isbn = "9783031159138",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "398--411",

editor = "Bekos, {Michael A.} and Michael Kaufmann",

booktitle = "Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers",

}

Martin, B, Paulusma, D, Smith, S & van Leeuwen, EJ 2022, Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. in MA Bekos & M Kaufmann (eds), Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13453 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 398-411, 48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022, Tübingen, Germany, 22/06/22. https://doi.org/10.1007/978-3-031-15914-5_29

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. / Martin, Barnaby; Paulusma, Daniël; Smith, Siani et al.
Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers. ed. / Michael A. Bekos; Michael Kaufmann. Springer Science and Business Media Deutschland GmbH, 2022. p. 398-411 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13453 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

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

PY - 2022

Y1 - 2022

N2 - Paths $$P^1,\ldots,P^k$$ in a graph $$G=(V,E)$$ are mutually induced if any two distinct $$P^i$$ 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^i$$ such that each $$P^i$$ 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.

AB - Paths $$P^1,\ldots,P^k$$ in a graph $$G=(V,E)$$ are mutually induced if any two distinct $$P^i$$ 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^i$$ such that each $$P^i$$ 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.

KW - complexity dichotomy

KW - connectivity

KW - H-free graph

KW - induced subgraphs

UR - http://www.scopus.com/inward/record.url?scp=85140765728&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-15914-5_29

DO - 10.1007/978-3-031-15914-5_29

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85140765728

SN - 9783031159138

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 398

EP - 411

BT - Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers

A2 - Bekos, Michael A.

A2 - Kaufmann, Michael

PB - Springer Science and Business Media Deutschland GmbH

T2 - 48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022

Y2 - 22 June 2022 through 24 June 2022

ER -

Martin B, Paulusma D, Smith S, van Leeuwen EJ. Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In Bekos MA, Kaufmann M, editors, Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2022. p. 398-411. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-15914-5_29