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.STACS.2019.39
URN: urn:nbn:de:0030-drops-102783
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10278/
Go to the corresponding LIPIcs Volume Portal

Jansen, Bart M. P. ; Pilipczuk, Marcin ; van Leeuwen, Erik Jan

A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs

pdf-format:
LIPIcs-STACS-2019-39.pdf (0.6 MB)

Abstract

We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs (FOCS 2014). It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem.

BibTeX - Entry

@InProceedings{jansen_et_al:LIPIcs:2019:10278,
  author =	{Bart M. P. Jansen and Marcin Pilipczuk and Erik Jan van Leeuwen},
  title =	{{A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10278},
  doi =		{10.4230/LIPIcs.STACS.2019.39},
  annote =	{Keywords: planar graphs, kernelization, odd cycle transversal, multiway cut}
}

Keywords: planar graphs, kernelization, odd cycle transversal, multiway cut
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

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