License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.151
URN: urn:nbn:de:0030-drops-55790
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5579/
Go to the corresponding LIPIcs Volume Portal

Suchý, Ondrj

Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices

pdf-format:
16.pdf (0.5 MB)

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

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