Steiner Trees for Hereditary Graph Classes
Publication date
2020
Authors
Bodlaender, H.L.
Brettell, Nick
Johnson, Matthew
Paesani, Giacomo
Paulusma, Daniël
van Leeuwen, Erik Jan
Editors
Kohayakawa, Yoshiharu
Miyazawa, Flávio Keidi
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
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. 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.
Keywords
Taverne, Theoretical Computer Science, General Computer Science
Citation
Bodlaender, H L, Brettell, N, Johnson, M, Paesani, G, Paulusma, D & van Leeuwen, E J 2020, Steiner Trees for Hereditary Graph Classes. in Y Kohayakawa & F K Miyazawa (eds), LATIN 2020 : Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12118 LNCS, Springer, pp. 613-624, 14th Latin American Symposium on Theoretical Informatics, LATIN 2020, Sao Paulo, Brazil, 5/01/21. https://doi.org/10.1007/978-3-030-61792-9_48, conference