Search Results

Documents authored by Suchý, Ondrj


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

Authors: Ondrj Suchý

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)


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.

Cite as

Ondrj Suchý. Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 151-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{suchy:LIPIcs.IPEC.2015.151,
  author =	{Such\'{y}, Ondrj},
  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 =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.151},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail