A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs

Bart M.P. Jansen, Marcin Pilipczuk, E.J. van Leeuwen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

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.
Original languageEnglish
Title of host publication36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
EditorsRolf Niedermeier, Christophe Paul
Pages39:1-39:18
Number of pages18
ISBN (Electronic)9783959771009
DOIs
Publication statusPublished - 1 Mar 2019
Event36th International Symposium on Theoretical Aspects of Computer Science - TU Berlin, Berlin, Germany
Duration: 13 Mar 201916 Mar 2019
https://stacs2019.akt.tu-berlin.de/

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume126
ISSN (Print)1868-8969

Conference

Conference36th International Symposium on Theoretical Aspects of Computer Science
Abbreviated titleSTACS 2019
Country/TerritoryGermany
CityBerlin
Period13/03/1916/03/19
Internet address

Keywords

  • Kernelization
  • Multiway cut
  • Odd cycle transversal
  • Planar graphs
  • odd cycle transversal
  • planar graphs
  • kernelization
  • multiway cut

Fingerprint

Dive into the research topics of 'A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs'. Together they form a unique fingerprint.

Cite this