Steiner trees for hereditary graph classes: a treewidth perspective (Q2663041)

The complexity of the Edge Steiner Tree and Vertex Steiner Tree problems is studied for classes of graphs characterized by a small set of forbidden induced subgraphs. Dichotomies are established for Edge Steiner Tree on \((H_1, H_2)\)-free graphs and for Vertex Steiner Tree on \(H\)-free graphs. It is shown that, assuming \(\mathrm{P} \neq \mathrm{NP}\), although there are infinitely many graphs \(H\) for which Vertex Steiner Tree is polynomial-time solvable for \(H\)-free graphs, there are only two graphs for which Edge Steiner Tree is polynomial-time solvable. Further, assuming that \(\mathrm{P} \neq \mathrm{NP}\), it is established that Edge Steiner Tree is 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. In the process of establishing this, all pairs \((H_1, H_2)\) for which the class of \((H_1, H_2)\)-free graphs has bounded treewidth are determined.