TY - JOUR
T1 - Steiner trees for hereditary graph classes
T2 - A treewidth perspective
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:
An extended abstract of this paper appeared in the proceedings of LATIN 2020 [3]. The paper received support from the Leverhulme Trust (RPG-2016-258) and the Royal Society (IES?R1?191223).
Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2021/5/6
Y1 - 2021/5/6
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 (assuming P≠NP). 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 (assuming P≠NP). 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.
KW - Hereditary graph class
KW - Steiner tree
KW - Treewidth
UR - http://www.scopus.com/inward/record.url?scp=85102650694&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2021.03.012
DO - 10.1016/j.tcs.2021.03.012
M3 - Article
AN - SCOPUS:85102650694
SN - 0304-3975
VL - 867
SP - 30
EP - 39
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -