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

N1 - Funding Information:
Supported by the Leverhulme Trust (RPG-2016-258) and the Royal (IES\R1\191223).
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

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 -