Steiner trees for hereditary graph classes: A treewidth perspective

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 ( 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 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 ( 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 ≠ 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.

Authors

• Hans L. Bodlaender
• Nick Brettell
• Matthew Johnson
• Giacomo Paesani University of Leeds
• Daniël Paulusma
• Erik Jan van Leeuwen

Keywords

• Steiner tree
• Hereditary graph class
• Treewidth