Steiner trees for hereditary graph classes: A treewidth perspective

We consider the classical problems(Edge) Steiner TreeandVertex Steiner Treeafter 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-1, H-2)free graphs and a dichotomy for the latter problem restricted to H-free graphs. We find that there exists an infinite family of graphs Hsuch thatVertex Steiner Treeis polynomial-time solvable for H-free graphs, whereas there exist only two graphs Hfor which this holds forEdge Steiner Tree(assuming P not equal NP). We also find thatEdge Steiner Treeis polynomial-time solvable for (H-1, H-2)-free graphs if and only if the treewidth of the class of (H-1, H-2)-free graphs is bounded (subject to P not equal NP). To obtain the latter result, we determine all pairs (H-1, H-2) for which the class of (H-1, H-2)-free graphs has bounded treewidth. (c) 2021 Elsevier B.V. All rights reserved.