Steiner trees for hereditary graph classes: A treewidth perspective

Hans L. Bodlaender; Nick Brettell; Matthew Johnson; Giacomo Paesani; Daniël Paulusma; Erik Jan van Leeuwen

doi:10.1016/j.tcs.2021.03.012

Steiner trees for hereditary graph classes: A treewidth perspective

Hans L. Bodlaender, Nick Brettell^*, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Erik Jan van Leeuwen

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

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 (H₁,H₂)-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₁,H₂)-free graphs if and only if the treewidth of the class of (H₁,H₂)-free graphs is bounded (subject to P≠NP). To obtain the latter result, we determine all pairs (H₁,H₂) for which the class of (H₁,H₂)-free graphs has bounded treewidth.

Original language	English
Pages (from-to)	30-39
Number of pages	10
Journal	Theoretical Computer Science
Volume	867
DOIs	https://doi.org/10.1016/j.tcs.2021.03.012
Publication status	Published - 6 May 2021

Bibliographical note

Funding Information:
An extended abstract of this paper appeared in the proceedings of LATIN 2020 [3]. The paper received support from the Leverhulme Trust (RPG-2016-258) and the Royal Society (IES?R1?191223).

Publisher Copyright:
© 2021 Elsevier B.V.

Funding

An extended abstract of this paper appeared in the proceedings of LATIN 2020 [3]. The paper received support from the Leverhulme Trust (RPG-2016-258) and the Royal Society (IES?R1?191223).

Keywords

Hereditary graph class
Steiner tree
Treewidth

Access to Document

10.1016/j.tcs.2021.03.012

1-s2.0-S0304397521001420-mainFinal published version, 372 KBLicence: Taverne

Cite this

@article{862902162a24478a8003342d4c14f242,

title = "Steiner trees for hereditary graph classes: A treewidth perspective",

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 (assuming P≠NP). 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 = "Hereditary graph class, Steiner tree, Treewidth",

author = "Bodlaender, {Hans L.} and Nick Brettell and Matthew Johnson and Giacomo Paesani and Dani{\"e}l Paulusma and {van Leeuwen}, {Erik Jan}",

note = "Funding Information: An extended abstract of this paper appeared in the proceedings of LATIN 2020 [3]. The paper received support from the Leverhulme Trust (RPG-2016-258) and the Royal Society (IES?R1?191223). Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = may,

day = "6",

doi = "10.1016/j.tcs.2021.03.012",

language = "English",

volume = "867",

pages = "30--39",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Steiner trees for hereditary graph classes

T2 - A treewidth perspective

AU - Bodlaender, Hans L.

AU - Brettell, Nick

AU - Johnson, Matthew

AU - Paesani, Giacomo

AU - Paulusma, Daniël

AU - van Leeuwen, Erik Jan

N1 - Funding Information: An extended abstract of this paper appeared in the proceedings of LATIN 2020 [3]. The paper received support from the Leverhulme Trust (RPG-2016-258) and the Royal Society (IES?R1?191223). Publisher Copyright: © 2021 Elsevier B.V.

PY - 2021/5/6

Y1 - 2021/5/6

N2 - 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 (assuming P≠NP). 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.

AB - 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 (assuming P≠NP). 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.

KW - Hereditary graph class

KW - Steiner tree

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85102650694&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2021.03.012

DO - 10.1016/j.tcs.2021.03.012

M3 - Article

AN - SCOPUS:85102650694

SN - 0304-3975

VL - 867

SP - 30

EP - 39

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Steiner trees for hereditary graph classes: A treewidth perspective

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this