Compression via Matroids
From MaRDI portal
Abstract: The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite by deleting at most of its vertices. In a breakthrough result Reed, Smith, and Vetta (Operations Research Letters, 2004) gave a time algorithm for it, the first algorithm with polynomial runtime of uniform degree for every fixed . It is known that this implies a polynomial-time compression algorithm that turns OCT instances into equivalent instances of size at most , a so-called kernelization. Since then the existence of a polynomial kernel for OCT, i.e., a kernelization with size bounded polynomially in , has turned into one of the main open questions in the study of kernelization. This work provides the first (randomized) polynomial kernelization for OCT. We introduce a novel kernelization approach based on matroid theory, where we encode all relevant information about a problem instance into a matroid with a representation of size polynomial in . For OCT, the matroid is built to allow us to simulate the computation of the iterative compression step of the algorithm of Reed, Smith, and Vetta, applied (for only one round) to an approximate odd cycle transversal which it is aiming to shrink to size . The process is randomized with one-sided error exponentially small in , where the result can contain false positives but no false negatives, and the size guarantee is cubic in the size of the approximate solution. Combined with an -approximation (Agarwal et al., STOC 2005), we get a reduction of the instance to size , implying a randomized polynomial kernelization.
Recommendations
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Exact and approximate compression of transfer matrices for graph homomorphisms
- Another disjoint compression algorithm for odd cycle transversal
- A Compression Algorithm for Probability Transition Matrices
- An O(N N) hierarchical random compression method for kernel matrices by sampling partial matrix entries
- Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
- Graph compression and the zeros of polynomials
- On the Compression of Low Rank Matrices
- \(\mathcal{H}^2\)-matrix compression
Cited in
(47)- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
- Another disjoint compression algorithm for odd cycle transversal
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- On polynomial kernels for structural parameterizations of odd cycle transversal
- Kernelization -- preprocessing with a guarantee
- On the kernelization complexity of problems on graphs without long odd cycles
- Subexponential parameterized odd cycle transversal on planar graphs
- Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
- Odd multiway cut in directed acyclic graphs
- Simpler parameterized algorithm for OCT
- A Compression Algorithm for Probability Transition Matrices
- Approximation and kernelization for chordal vertex deletion
- Exploring the kernelization borders for hitting cycles
- Multi-budgeted directed cuts
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Proximity Search for Maximal Subgraph Enumeration
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- An Updated Experimental Evaluation of Graph Bipartization Methods
- Representative sets and irrelevant vertices: new tools for kernelization
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Hitting selected (odd) cycles
- Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Linear representation of transversal matroids and gammoids parameterized by rank
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- scientific article; zbMATH DE number 7765420 (Why is no real title available?)
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- A survey of parameterized algorithms and the complexity of edge modification
- On Weighted Graph Separation Problems and Flow Augmentation
- Edge bipartization faster than \(2^k\)
- A constant-factor approximation for weighted bond cover
- On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
- Bipartizing (pseudo-)disk graphs: approximation with a ratio better than 3
- Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
- Odd cycle transversal on P₅-free graphs in polynomial time
- True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
- Exploiting dense structures in parameterized complexity
- Preprocessing to reduce the search space for odd cycle transversal
- Faster algorithms on linear delta-matroids
- Efficient parameterized approximation
- Polynomial kernels with reachability for weighted d-matroid intersection
- Boundaried kernelization via representative sets
- Fair short paths in vertex-colored graphs
- Multi-budgeted directed cuts
This page was built for publication: Compression via Matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962154)
