Steiner Trees for Hereditary Graph Classes

Hans L. Bodlaender; Nick Brettell; Matthew Johnson; Giacomo Paesani; Daniël Paulusma; Erik Jan van Leeuwen

doi:10.1007/978-3-030-61792-9_48

Steiner Trees for Hereditary Graph Classes

Hans L. Bodlaender, Nick Brettell^*, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Erik Jan van Leeuwen

^*Corresponding author for this work

Durham University

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

Abstract

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (H₁, H₂) -free graphs and a dichotomy for the latter problem restricted to H-free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H-free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree. We also find that Edge Steiner Tree is polynomial-time solvable for (H₁, H₂) -free graphs if and only if the treewidth of the class of (H₁, H₂) -free graphs is bounded (subject to P≠ NP). To obtain the latter result, we determine all pairs (H₁, H₂) for which the class of (H₁, H₂) -free graphs has bounded treewidth.

Original language	English
Title of host publication	LATIN 2020
Subtitle of host publication	Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings
Editors	Yoshiharu Kohayakawa, Flávio Keidi Miyazawa
Publisher	Springer
Pages	613-624
Number of pages	12
ISBN (Print)	9783030617912
DOIs	https://doi.org/10.1007/978-3-030-61792-9_48
Publication status	Published - 2020
Event	14th Latin American Symposium on Theoretical Informatics, LATIN 2020 - Sao Paulo, Brazil Duration: 5 Jan 2021 → 8 Jan 2021

Publication series

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

Conference

Conference	14th Latin American Symposium on Theoretical Informatics, LATIN 2020
Country/Territory	Brazil
City	Sao Paulo
Period	5/01/21 → 8/01/21

Bibliographical note

Funding Information:
Supported by the Leverhulme Trust (RPG-2016-258) and the Royal (IES\R1\191223).

Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

Funding

Supported by the Leverhulme Trust (RPG-2016-258) and the Royal (IES\R1\191223).

Access to Document

10.1007/978-3-030-61792-9_48

Bodlaender2020_Chapter_SteinerTreesForHereditaryGraphFinal published version, 443 KBLicence: Taverne

Cite this

Bodlaender, H. L., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2020). Steiner Trees for Hereditary Graph Classes. In Y. Kohayakawa, & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings (pp. 613-624). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12118 LNCS). Springer. https://doi.org/10.1007/978-3-030-61792-9_48

Bodlaender, Hans L. ; Brettell, Nick ; Johnson, Matthew et al. / Steiner Trees for Hereditary Graph Classes. LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. editor / Yoshiharu Kohayakawa ; Flávio Keidi Miyazawa. Springer, 2020. pp. 613-624 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9f56222841ac4bccb4ad9389441071b4,

title = "Steiner Trees for Hereditary Graph Classes",

abstract = "We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (H1, H2) -free graphs and a dichotomy for the latter problem restricted to H-free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H-free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree. We also find that Edge Steiner Tree is polynomial-time solvable for (H1, H2) -free graphs if and only if the treewidth of the class of (H1, H2) -free graphs is bounded (subject to P≠ NP). To obtain the latter result, we determine all pairs (H1, H2) for which the class of (H1, H2) -free graphs has bounded treewidth.",

author = "Bodlaender, {Hans L.} and Nick Brettell and Matthew Johnson and Giacomo Paesani and Dani{\"e}l Paulusma and {van Leeuwen}, {Erik Jan}",

note = "Funding Information: Supported by the Leverhulme Trust (RPG-2016-258) and the Royal (IES\R1\191223). Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 14th Latin American Symposium on Theoretical Informatics, LATIN 2020 ; Conference date: 05-01-2021 Through 08-01-2021",

year = "2020",

doi = "10.1007/978-3-030-61792-9_48",

language = "English",

isbn = "9783030617912",

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

publisher = "Springer",

pages = "613--624",

editor = "Yoshiharu Kohayakawa and Miyazawa, {Fl{\'a}vio Keidi}",

booktitle = "LATIN 2020",

}

Bodlaender, HL, Brettell, N, Johnson, M, Paesani, G, Paulusma, D & van Leeuwen, EJ 2020, Steiner Trees for Hereditary Graph Classes. in Y Kohayakawa & FK Miyazawa (eds), LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12118 LNCS, Springer, pp. 613-624, 14th Latin American Symposium on Theoretical Informatics, LATIN 2020, Sao Paulo, Brazil, 5/01/21. https://doi.org/10.1007/978-3-030-61792-9_48

Steiner Trees for Hereditary Graph Classes. / Bodlaender, Hans L.; Brettell, Nick; Johnson, Matthew et al.
LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. ed. / Yoshiharu Kohayakawa; Flávio Keidi Miyazawa. Springer, 2020. p. 613-624 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12118 LNCS).

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

TY - GEN

T1 - Steiner Trees for Hereditary Graph Classes

AU - Bodlaender, Hans L.

AU - Brettell, Nick

AU - Johnson, Matthew

AU - Paesani, Giacomo

AU - Paulusma, Daniël

AU - van Leeuwen, Erik Jan

PY - 2020

Y1 - 2020

N2 - We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (H1, H2) -free graphs and a dichotomy for the latter problem restricted to H-free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H-free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree. We also find that Edge Steiner Tree is polynomial-time solvable for (H1, H2) -free graphs if and only if the treewidth of the class of (H1, H2) -free graphs is bounded (subject to P≠ NP). To obtain the latter result, we determine all pairs (H1, H2) for which the class of (H1, H2) -free graphs has bounded treewidth.

AB - We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (H1, H2) -free graphs and a dichotomy for the latter problem restricted to H-free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H-free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree. We also find that Edge Steiner Tree is polynomial-time solvable for (H1, H2) -free graphs if and only if the treewidth of the class of (H1, H2) -free graphs is bounded (subject to P≠ NP). To obtain the latter result, we determine all pairs (H1, H2) for which the class of (H1, H2) -free graphs has bounded treewidth.

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

U2 - 10.1007/978-3-030-61792-9_48

DO - 10.1007/978-3-030-61792-9_48

M3 - Conference contribution

AN - SCOPUS:85097718622

SN - 9783030617912

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

SP - 613

EP - 624

BT - LATIN 2020

A2 - Kohayakawa, Yoshiharu

A2 - Miyazawa, Flávio Keidi

PB - Springer

T2 - 14th Latin American Symposium on Theoretical Informatics, LATIN 2020

Y2 - 5 January 2021 through 8 January 2021

ER -

Bodlaender HL, Brettell N, Johnson M, Paesani G, Paulusma D, van Leeuwen EJ. Steiner Trees for Hereditary Graph Classes. In Kohayakawa Y, Miyazawa FK, editors, LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Springer. 2020. p. 613-624. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-61792-9_48

Steiner Trees for Hereditary Graph Classes

Abstract

Publication series

Conference

Bibliographical note

Funding

Access to Document

Other files and links

Fingerprint

Cite this