Abstract
In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The vertices in the subset T are called terminals and the other vertices are called Steiner vertices. Recently, Pilipczuk, Pilipczuk, Sankowski, and van Leeuwen [FOCS 2014] gave a polynomial kernel for Steiner Tree in planar graphs, when parameterized by |T|+k, the total number of vertices in the constructed subgraph.
In this paper we present several polynomial time applicable reduction rules for Planar Steiner Tree. In an instance reduced with respect to the presented reduction rules, the number of terminals |T| is at most quadratic in the number of other vertices k in the subgraph. Hence, using and improving the result of Pilipczuk et al., we give a polynomial kernel for Steiner Tree in planar graphs for the parameterization by the number k of Steiner vertices in the solution.
BibTeX - Entry
@InProceedings{such:LIPIcs:2015:5579,
author = {Ondrj Such{\'y}},
title = {{Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {151--162},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-92-7},
ISSN = {1868-8969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5579},
URN = {urn:nbn:de:0030-drops-55790},
doi = {10.4230/LIPIcs.IPEC.2015.151},
annote = {Keywords: Steiner Tree, polynomial kernel, planar graphs, polynomial-time preprocessing, network sparsification}
}
|
Keywords: |
|
Steiner Tree, polynomial kernel, planar graphs, polynomial-time preprocessing, network sparsification |
|
Collection: |
|
10th International Symposium on Parameterized and Exact Computation (IPEC 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
19.11.2015 |
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)