2026-07-20T10:52:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5579 2024-03-06T10:36:35Z ddc:004 open_access

Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices Suchý, Ondrj Steiner Tree polynomial kernel planar graphs polynomial-time preprocessing network sparsification 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ondrj Suchý 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.151 urn:nbn:de:0030-drops-55790 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.151 eng https://creativecommons.org/licenses/by/3.0/legalcode