A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs

DOI10.4230/LIPICS.STACS.2019.39MaRDI QIDQ5090489zbMATH OpenOpenAlexFDO

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

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2019.39

zbMATH Keywords

kernelizationmultiway cutodd cycle transversalplanar graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• Compression via Matroids
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• Kernelization for cycle transversal problems
• On the small cycle transversal of planar graphs

Cites work

• A near-optimal planarization algorithm
• Bidimensionality and kernels
• Compression via Matroids
• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• FPT algorithms for path-transversal and cycle-transversal problems
• Fundamentals of parameterized complexity
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization -- preprocessing with a guarantee
• Multiway cuts in node weighted graphs
• Network sparsification for Steiner problems on planar and bounded-genus graphs
• New limits to classical and quantum instance compression
• Obtaining a planar graph by vertex deletion
• On problems without polynomial kernels
• Parameterized algorithms
• Planar graph bipartization in linear time
• Planarity Allowing Few Error Vertices in Linear Time
• Polynomial kernels for hard problems on disk graphs
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Subexponential-time parameterized algorithm for Steiner tree on planar graphs

Cited in

(6)

• Odd multiway cut in directed acyclic graphs
• Quick separation in chordal and split graphs
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs

This page was built for publication: A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090489)