Disjoint Paths and Connected Subgraphs for H-Free Graphs

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

doi:10.1007/978-3-030-79987-8_29

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

Mathematics of Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (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 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.

Original language	English
Title of host publication	Combinatorial Algorithms
Subtitle of host publication	32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings
Editors	Paola Flocchini, Lucia Moura
Place of Publication	Cham
Publisher	Springer
Pages	414-427
Number of pages	14
ISBN (Electronic)	978-3-030-79987-8
ISBN (Print)	978-3-030-79986-1
DOIs	https://doi.org/10.1007/978-3-030-79987-8_29
Publication status	Published - 2021
Event	32nd International Workshop on Combinatorial Algorithms, IWOCA 2021 - Virtual, Online Duration: 5 Jul 2021 → 7 Jul 2021 Conference number: 32

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12757
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	32nd International Workshop on Combinatorial Algorithms, IWOCA 2021
Abbreviated title	IWOCA 2021
City	Virtual, Online
Period	5/07/21 → 7/07/21

Keywords

n/a OA procedure

Access to Document

10.1007/978-3-030-79987-8_29

Cite this

Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2021). Disjoint Paths and Connected Subgraphs for H-Free Graphs. In P. Flocchini, & L. Moura (Eds.), Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings (pp. 414-427). (Lecture Notes in Computer Science; Vol. 12757). Springer. https://doi.org/10.1007/978-3-030-79987-8_29

@inproceedings{55baa543b73c48b2a4f97067cddc0659,

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

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 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.",

keywords = "n/a OA procedure",

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

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021, IWOCA 2021 ; Conference date: 05-07-2021 Through 07-07-2021",

year = "2021",

doi = "10.1007/978-3-030-79987-8_29",

language = "English",

isbn = "978-3-030-79986-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "414--427",

editor = "Paola Flocchini and Lucia Moura",

booktitle = "Combinatorial Algorithms",

address = "Germany",

}

Kern, W, Martin, B, Paulusma, D, Smith, S & van Leeuwen, EJ 2021, Disjoint Paths and Connected Subgraphs for H-Free Graphs. in P Flocchini & L Moura (eds), Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12757, Springer, Cham, pp. 414-427, 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021, Virtual, Online, 5/07/21. https://doi.org/10.1007/978-3-030-79987-8_29

Disjoint Paths and Connected Subgraphs for H-Free Graphs. / Kern, Walter; Martin, Barnaby; Paulusma, Daniël et al.
Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings. ed. / Paola Flocchini; Lucia Moura. Cham: Springer, 2021. p. 414-427 (Lecture Notes in Computer Science; Vol. 12757).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Kern, Walter

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

AU - van Leeuwen, Erik Jan

N1 - Conference code: 32

PY - 2021

Y1 - 2021

N2 - 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 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.

AB - 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 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.

KW - n/a OA procedure

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

U2 - 10.1007/978-3-030-79987-8_29

DO - 10.1007/978-3-030-79987-8_29

M3 - Conference contribution

AN - SCOPUS:85111953680

SN - 978-3-030-79986-1

T3 - Lecture Notes in Computer Science

SP - 414

EP - 427

BT - Combinatorial Algorithms

A2 - Flocchini, Paola

A2 - Moura, Lucia

PB - Springer

CY - Cham

T2 - 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021

Y2 - 5 July 2021 through 7 July 2021

ER -

Disjoint Paths and Connected Subgraphs for H-Free Graphs

Abstract

Publication series

Workshop

Keywords

Access to Document

Other files and links

Fingerprint

Cite this