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 QIDQ5090489
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
Related Items (3)
Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Quick separation in chordal and split graphs
Cites Work
- Fundamentals of parameterized complexity
- FPT algorithms for path-transversal and cycle-transversal problems
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- On problems without polynomial kernels
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Obtaining a planar graph by vertex deletion
- Planar graph bipartization in linear time
- On Multiway Cut Parameterized above Lower Bounds
- Kernelization – Preprocessing with a Guarantee
- Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
- Uniform Kernelization Complexity of Hitting Forbidden Minors
- New Limits to Classical and Quantum Instance Compression
- Polynomial Kernels for Hard Problems on Disk Graphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- Multiway cuts in node weighted graphs
- Compression via Matroids
- Planarity Allowing Few Error Vertices in Linear Time
- A Near-Optimal Planarization Algorithm
- Bidimensionality and Geometric Graphs
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
This page was built for publication: A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
