PTAS for Steiner Tree on Map Graphs

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-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 languageEnglish
Title of host publicationLATIN 2020
Subtitle of host publicationTheoretical Informatics - 14th Latin American Symposium 2021, Proceedings
EditorsYoshiharu Kohayakawa, Flávio Keidi Miyazawa
Pages3-14
Number of pages12
DOIs
Publication statusPublished - 2020
MoE publication typeA4 Article in a conference publication
EventLatin American Symposium on Theoretical Informatics - Sao Paulo, Brazil
Duration: 5 Jan 20218 Jan 2021
Conference number: 14

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume12118 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceLatin American Symposium on Theoretical Informatics
Abbreviated titleLATIN
CountryBrazil
CitySao Paulo
Period05/01/202108/01/2021

Fingerprint Dive into the research topics of 'PTAS for Steiner Tree on Map Graphs'. Together they form a unique fingerprint.

Cite this