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 -