文章基本信息

标题：Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
本地全文：下载
作者：Marcin Pilipczuk ; Michal Pilipczuk ; Piotr Sankowski 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：20
页码：353-364
DOI：10.4230/LIPIcs.STACS.2013.353
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：planar graph; Steiner tree; subexponential-time algorithms