License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.353
URN: urn:nbn:de:0030-drops-39471
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3947/
Go to the corresponding LIPIcs Volume Portal

Pilipczuk, Marcin ; Pilipczuk, Michal ; Sankowski, Piotr ; van Leeuwen, Erik Jan

Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs

pdf-format:
35.pdf (0.6 MB)

Abstract

The well-known bidimensionality theory provides a method for designing fast, subexponential-time parameterized algorithms for a vast number of NP-hard problems on sparse graph classes such as planar graphs, bounded genus graphs, or, more generally, graphs with a fixed excluded minor. However, in order to apply the bidimensionality framework the considered problem needs to fulfill a special density property. Some well-known problems do not have this property, unfortunately, with probably the most prominent and important example being the Steiner Tree problem. Hence the question whether a subexponential-time parameterized algorithm for Steiner Tree on planar graphs exists has remained open. In this paper, we answer this question positively and develop an algorithm running in O(2^{O((k log k)^{2/3})}n) time and polynomial space, where k is the size of the Steiner tree and n is the number of vertices of the graph.
Our algorithm does not rely on tools from bidimensionality theory or graph minors theory, apart from Baker's classical approach. Instead, we introduce new tools and concepts to the study of the parameterized complexity of problems on sparse graphs.

BibTeX - Entry

@InProceedings{pilipczuk_et_al:LIPIcs:2013:3947,
  author =	{Marcin Pilipczuk and Michal Pilipczuk and Piotr Sankowski and Erik Jan van Leeuwen},
  title =	{{Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{353--364},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3947},
  URN =		{urn:nbn:de:0030-drops-39471},
  doi =		{10.4230/LIPIcs.STACS.2013.353},
  annote =	{Keywords: planar graph, Steiner tree, subexponential-time algorithms}
}

Keywords: planar graph, Steiner tree, subexponential-time algorithms
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI