H.L. Bodlaender
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
Bodlaender, H.L.; Brettell, N.; Johnson, M.; Paesani, G.; Paulusma, D.; van Leeuwen, E.J.
Authors
N. Brettell
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
G. Paesani
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
E.J. van Leeuwen
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 -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 ). We also find that Edge Steiner Tree is polynomial-time solvable for -free graphs if and only if the treewidth of the class of -free graphs is bounded (subject to ). To obtain the latter result, we determine all pairs for which the class of -free graphs has bounded treewidth.
Citation
Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. (2021). Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective. Theoretical Computer Science, 867, 30-39. https://doi.org/10.1016/j.tcs.2021.03.012
Journal Article Type | Article |
---|---|
Acceptance Date | Mar 4, 2021 |
Online Publication Date | Mar 10, 2021 |
Publication Date | May 6, 2021 |
Deposit Date | Mar 15, 2021 |
Publicly Available Date | Mar 10, 2022 |
Journal | Theoretical Computer Science |
Print ISSN | 0304-3975 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 867 |
Pages | 30-39 |
DOI | https://doi.org/10.1016/j.tcs.2021.03.012 |
Public URL | https://durham-repository.worktribe.com/output/1245461 |
Files
Accepted Journal Article
(487 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs
(2021)
Presentation / Conference Contribution
Computing subset transversals in H-free graphs
(2021)
Journal Article
Bounding the mim-width of hereditary graph classes
(2021)
Journal Article
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
(2020)
Journal Article
Computing subset transversals in H-free graphs
(2020)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search