Compression via matroids: a randomized polynomial kernel for odd cycle transversal
From MaRDI portal
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
Cites work
- (Meta) Kernelization
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
- \textsc{Multicut} is FPT
- A 4k^2 kernel for feedback vertex set
- A Cubic Kernel for Feedback Vertex Set
- A faster fixed-parameter approach to drawing binary tanglegrams
- A fixed-parameter algorithm for the directed feedback vertex set problem
- A parameterized view on matroid optimization problems
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- Algorithm Engineering for Optimal Graph Bipartization
- Almost 2-SAT is fixed-parameter tractable
- An improved parameterized algorithm for the minimum node multiway cut problem
- Applications of Menger's graph theorem
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Bidimensionality and kernels
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Comparing trees via crossing minimization
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Experimental and Efficient Algorithms
- Finding odd cycle transversals.
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- scientific article; zbMATH DE number 6297714 (Why is no real title available?)
- scientific article; zbMATH DE number 6297727 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Incompressibility through Colors and IDs
- Infeasibility of instance compression and succinct PCPs for NP
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Kernels for feedback arc set in tournaments
- Lower bounds on kernelization
- On problems without polynomial kernels
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- On the power of unique 2-prover 1-round games
- Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10--11, 2009. Revised selected papers
- Parameterized graph separation problems
- Parametrized complexity theory.
- Planar graph bipartization in linear time
- PRIMES is in P
- Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011.
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Separator-based data reduction for signed graph balancing
- Simpler parameterized algorithm for OCT
- The multi-multiway cut problem
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Two edge modification problems without polynomial kernels
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
- Wheel-Free Deletion Is W[2]-Hard
Cited in
(11)- A completeness theory for polynomial (Turing) kernelization
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- On polynomial kernels for structural parameterizations of odd cycle transversal
- On the kernelization complexity of problems on graphs without long odd cycles
- Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
- New limits to classical and quantum instance compression
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- A Compression Algorithm for Probability Transition Matrices
- Compression via Matroids
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- Representative sets and irrelevant vertices: new tools for kernelization
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)
