Steiner trees for hereditary graph classes: a treewidth perspective (Q2663041)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Steiner trees for hereditary graph classes: a treewidth perspective |
scientific article |
Statements
Steiner trees for hereditary graph classes: a treewidth perspective (English)
0 references
15 April 2021
0 references
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.
0 references
Steiner tree
0 references
hereditary graph class
0 references
treewidth
0 references
0 references