PTAS for Steiner Tree on Map Graphs

Jarosław Byrka; Mateusz Lewandowski; Syed Mohammad Meesum; Joachim Spoerhase; Sumedha Uniyal

doi:10.1007/978-3-030-61792-9_1

PTAS for Steiner Tree on Map Graphs

Jarosław Byrka, Mateusz Lewandowski^*, Syed Mohammad Meesum, Joachim Spoerhase, Sumedha Uniyal

^*Corresponding author for this work

University of Wrocław

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

Abstract

We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i. e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.

Original language	English
Title of host publication	LATIN 2020
Subtitle of host publication	Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings
Editors	Yoshiharu Kohayakawa, Flávio Keidi Miyazawa
Publisher	Springer
Pages	3-14
Number of pages	12
ISBN (Print)	9783030617912
DOIs	https://doi.org/10.1007/978-3-030-61792-9_1
Publication status	Published - 2020
MoE publication type	A4 Conference publication
Event	Latin American Symposium on Theoretical Informatics - Sao Paulo, Brazil Duration: 5 Jan 2021 → 8 Jan 2021 Conference number: 14

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	12118 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Latin American Symposium on Theoretical Informatics
Abbreviated title	LATIN
Country/Territory	Brazil
City	Sao Paulo
Period	05/01/2021 → 08/01/2021

Access to Document

10.1007/978-3-030-61792-9_1

https://arxiv.org/abs/1912.00717

Cite this

Byrka, J., Lewandowski, M., Meesum, S. M., Spoerhase, J., & Uniyal, S. (2020). PTAS for Steiner Tree on Map Graphs. In Y. Kohayakawa, & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings (pp. 3-14). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12118 LNCS). Springer. https://doi.org/10.1007/978-3-030-61792-9_1

Byrka, Jarosław ; Lewandowski, Mateusz ; Meesum, Syed Mohammad et al. / PTAS for Steiner Tree on Map Graphs. LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. editor / Yoshiharu Kohayakawa ; Flávio Keidi Miyazawa. Springer, 2020. pp. 3-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0aad7f5b46114016a73d197c01148003,

title = "PTAS for Steiner Tree on Map Graphs",

abstract = "We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i. e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.",

author = "Jaros{\l}aw Byrka and Mateusz Lewandowski and Meesum, {Syed Mohammad} and Joachim Spoerhase and Sumedha Uniyal",

year = "2020",

doi = "10.1007/978-3-030-61792-9_1",

language = "English",

isbn = "9783030617912",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "3--14",

editor = "Yoshiharu Kohayakawa and Miyazawa, {Fl{\'a}vio Keidi}",

booktitle = "LATIN 2020",

address = "Germany",

note = "Latin American Symposium on Theoretical Informatics, LATIN ; Conference date: 05-01-2021 Through 08-01-2021",

}

Byrka, J, Lewandowski, M, Meesum, SM, Spoerhase, J & Uniyal, S 2020, PTAS for Steiner Tree on Map Graphs. in Y Kohayakawa & FK 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. 3-14, Latin American Symposium on Theoretical Informatics, Sao Paulo, Brazil, 05/01/2021. https://doi.org/10.1007/978-3-030-61792-9_1

PTAS for Steiner Tree on Map Graphs. / Byrka, Jarosław; Lewandowski, Mateusz; Meesum, Syed Mohammad et al.
LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. ed. / Yoshiharu Kohayakawa; Flávio Keidi Miyazawa. Springer, 2020. p. 3-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12118 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - PTAS for Steiner Tree on Map Graphs

AU - Byrka, Jarosław

AU - Lewandowski, Mateusz

AU - Meesum, Syed Mohammad

AU - Spoerhase, Joachim

AU - Uniyal, Sumedha

N1 - Conference code: 14

PY - 2020

Y1 - 2020

N2 - We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i. e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.

AB - We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i. e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.

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

U2 - 10.1007/978-3-030-61792-9_1

DO - 10.1007/978-3-030-61792-9_1

M3 - Conference article in proceedings

AN - SCOPUS:85097715149

SN - 9783030617912

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 14

BT - LATIN 2020

A2 - Kohayakawa, Yoshiharu

A2 - Miyazawa, Flávio Keidi

PB - Springer

T2 - Latin American Symposium on Theoretical Informatics

Y2 - 5 January 2021 through 8 January 2021

ER -

Byrka J, Lewandowski M, Meesum SM, Spoerhase J, Uniyal S. PTAS for Steiner Tree on Map Graphs. In Kohayakawa Y, Miyazawa FK, editors, LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Springer. 2020. p. 3-14. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-61792-9_1

PTAS for Steiner Tree on Map Graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this