Compression via matroids: a randomized polynomial kernel for odd cycle transversal

zbMATH Open1423.68217MaRDI QIDQ5743380FDOQ5743380

Authors: Stefan Kratsch, Magnus Wahlström

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095124

Recommendations

Compression via Matroids
On polynomial kernels for structural parameterizations of odd cycle transversal
Subexponential parameterized odd cycle transversal on planar graphs
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
Kernelization for cycle transversal problems

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

Fundamentals of parameterized complexity
On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
Title not available (Why is that?)
Finding odd cycle transversals.
On problems without polynomial kernels
Almost 2-SAT is fixed-parameter tractable
Combinatorial optimization. Polyhedra and efficiency (3 volumes)
Parametrized complexity theory.
A \(4k^2\) kernel for feedback vertex set
A fixed-parameter algorithm for the directed feedback vertex set problem
Incompressibility through Colors and IDs
Fixed-parameter tractability of multicut parameterized by the size of the cutset
Title not available (Why is that?)
Parameterized graph separation problems
Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
PRIMES is in P
Vertex packings: Structural properties and algorithms
(Meta) Kernelization
Bidimensionality and kernels
Infeasibility of instance compression and succinct PCPs for NP
On the power of unique 2-prover 1-round games
Planar graph bipartization in linear time
An improved parameterized algorithm for the minimum node multiway cut problem
Applications of Menger's graph theorem
Algorithm Engineering for Optimal Graph Bipartization
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
\textsc{Multicut} is FPT
The multi-multiway cut problem
The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
Iterative Compression for Exactly Solving NP-Hard Minimization Problems
\(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
Vertex cover: Further observations and further improvements
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
Separator-based data reduction for signed graph balancing
Kernels for feedback arc set in tournaments
Kernel Bounds for Disjoint Cycles and Disjoint Paths
On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
Two edge modification problems without polynomial kernels
Title not available (Why is that?)
Simpler parameterized algorithm for OCT
A faster fixed-parameter approach to drawing binary tanglegrams
A parameterized view on matroid optimization problems
A Cubic Kernel for Feedback Vertex Set
Lower bounds on kernelization
Experimental and Efficient Algorithms
Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10--11, 2009. Revised selected papers
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
Title not available (Why is that?)
Comparing trees via crossing minimization
Wheel-Free Deletion Is W[2]-Hard
FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011.

Cited In (11)

On polynomial kernels for structural parameterizations of odd cycle transversal
Representative sets and irrelevant vertices: new tools for kernelization
A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
Preprocessing subgraph and minor problems: when does a small vertex cover help?
New limits to classical and quantum instance compression
Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
A Compression Algorithm for Probability Transition Matrices
A completeness theory for polynomial (Turing) kernelization
Compression via Matroids
Abusing the Tutte matrix: an algebraic instance compression for the \(K\)-set-cycle problem
On the kernelization complexity of problems on graphs without long odd cycles

This page was built for publication: Compression via matroids: a randomized polynomial kernel for odd cycle transversal

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