A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
From MaRDI portal
Publication:5090489
DOI10.4230/LIPICS.STACS.2019.39OpenAlexW2963874021MaRDI QIDQ5090489FDOQ5090489
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
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
- Fundamentals of parameterized complexity
- On problems without polynomial kernels
- Kernelization -- preprocessing with a guarantee
- FPT algorithms for path-transversal and cycle-transversal problems
- Multiway cuts in node weighted graphs
- Parameterized algorithms
- Bidimensionality and kernels
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Infeasibility of instance compression and succinct PCPs for NP
- Planar graph bipartization in linear time
- New limits to classical and quantum instance compression
- Kernel bounds for disjoint cycles and disjoint paths
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Obtaining a planar graph by vertex deletion
- Subexponential-time parameterized algorithm for Steiner tree on planar graphs
- Compression via Matroids
- A near-optimal planarization algorithm
- Polynomial kernels for hard problems on disk graphs
- Network sparsification for Steiner problems on planar and bounded-genus graphs
- Planarity Allowing Few Error Vertices in Linear Time
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
Cited In (5)
- Quick separation in chordal and split graphs
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- Odd multiway cut in directed acyclic 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)
