A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K4-Minor

Carla Groenland; Jesper Nederlof; Tomohiro Koana

doi:10.4230/LIPIcs.IPEC.2024.12

A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K₄-Minor

Carla Groenland^*
, Jesper Nederlof^*
, Tomohiro Koana^*

^*Corresponding author for this work

Sub Algorithms and Complexity

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that this problem can be solved in O(n⁴) time, where n denotes the number of vertices in the input graph. This generalizes a seminal paper by Erickson et al. [Math. Oper. Res., 1987] that solves Steiner tree on planar graphs with all terminals on one face in polynomial time.

Original language	English
Title of host publication	19th International Symposium on Parameterized and Exact Computation, IPEC 2024
Editors	Edouard Bonnet, Pawel Rzazewski
Publisher	Dagstuhl Publishing
ISBN (Electronic)	9783959773539
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2024.12
Publication status	Published - 5 Dec 2024
Event	19th International Symposium on Parameterized and Exact Computation, IPEC 2024 - London, United Kingdom Duration: 4 Sept 2024 → 6 Sept 2024

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	321
ISSN (Print)	1868-8969

Conference

Conference	19th International Symposium on Parameterized and Exact Computation, IPEC 2024
Country/Territory	United Kingdom
City	London
Period	4/09/24 → 6/09/24

Bibliographical note

Publisher Copyright:
© Carla Groenland, Jesper Nederlof, and Tomohiro Koana.

Keywords

rooted minor
Steiner tree

Access to Document

10.4230/LIPIcs.IPEC.2024.12Licence: CC BY

LIPIcs.IPEC.2024.12Final published version, 855 KBLicence: CC BY

Cite this

Groenland, C., Nederlof, J., & Koana, T. (2024). A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K₄-Minor. In E. Bonnet, & P. Rzazewski (Eds.), 19th International Symposium on Parameterized and Exact Computation, IPEC 2024 Article 12 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 321). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.IPEC.2024.12

@inproceedings{3afb9c5beb3446a1a4892deac8de794a,

title = "A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K4-Minor",

abstract = "We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that this problem can be solved in O(n4) time, where n denotes the number of vertices in the input graph. This generalizes a seminal paper by Erickson et al. [Math. Oper. Res., 1987] that solves Steiner tree on planar graphs with all terminals on one face in polynomial time.",

keywords = "rooted minor, Steiner tree",

author = "Carla Groenland and Jesper Nederlof and Tomohiro Koana",

note = "Publisher Copyright: {\textcopyright} Carla Groenland, Jesper Nederlof, and Tomohiro Koana.; 19th International Symposium on Parameterized and Exact Computation, IPEC 2024 ; Conference date: 04-09-2024 Through 06-09-2024",

year = "2024",

month = dec,

day = "5",

doi = "10.4230/LIPIcs.IPEC.2024.12",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Dagstuhl Publishing",

editor = "Edouard Bonnet and Pawel Rzazewski",

booktitle = "19th International Symposium on Parameterized and Exact Computation, IPEC 2024",

}

Groenland, C, Nederlof, J & Koana, T 2024, A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K₄-Minor. in E Bonnet & P Rzazewski (eds), 19th International Symposium on Parameterized and Exact Computation, IPEC 2024., 12, Leibniz International Proceedings in Informatics, LIPIcs, vol. 321, Dagstuhl Publishing, 19th International Symposium on Parameterized and Exact Computation, IPEC 2024, London, United Kingdom, 4/09/24. https://doi.org/10.4230/LIPIcs.IPEC.2024.12

A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K₄-Minor. / Groenland, Carla; Nederlof, Jesper; Koana, Tomohiro.
19th International Symposium on Parameterized and Exact Computation, IPEC 2024. ed. / Edouard Bonnet; Pawel Rzazewski. Dagstuhl Publishing, 2024. 12 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 321).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K4-Minor

AU - Groenland, Carla

AU - Nederlof, Jesper

AU - Koana, Tomohiro

PY - 2024/12/5

Y1 - 2024/12/5

N2 - We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that this problem can be solved in O(n4) time, where n denotes the number of vertices in the input graph. This generalizes a seminal paper by Erickson et al. [Math. Oper. Res., 1987] that solves Steiner tree on planar graphs with all terminals on one face in polynomial time.

AB - We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that this problem can be solved in O(n4) time, where n denotes the number of vertices in the input graph. This generalizes a seminal paper by Erickson et al. [Math. Oper. Res., 1987] that solves Steiner tree on planar graphs with all terminals on one face in polynomial time.

KW - rooted minor

KW - Steiner tree

UR - https://www.scopus.com/pages/publications/85213351393

U2 - 10.4230/LIPIcs.IPEC.2024.12

DO - 10.4230/LIPIcs.IPEC.2024.12

M3 - Conference contribution

AN - SCOPUS:85213351393

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 19th International Symposium on Parameterized and Exact Computation, IPEC 2024

A2 - Bonnet, Edouard

A2 - Rzazewski, Pawel

PB - Dagstuhl Publishing

T2 - 19th International Symposium on Parameterized and Exact Computation, IPEC 2024

Y2 - 4 September 2024 through 6 September 2024

ER -