Compression via Matroids

DOI10.1145/2635810MaRDI QIDQ4962154zbMATH OpenOpenAlexFDO

Authors Stefan Kratsch, Magnus Wahlström

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.3068

zbMATH Keywords

parameterized complexitykernelizationmatroidsodd cycle transversal

Mathematics Subject Classification ID

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

Abstract: The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite by deleting at most $k$ of its vertices. In a breakthrough result Reed, Smith, and Vetta (Operations Research Letters, 2004) gave a $BigOh(4^{k}kmn)$ time algorithm for it, the first algorithm with polynomial runtime of uniform degree for every fixed $k$. It is known that this implies a polynomial-time compression algorithm that turns OCT instances into equivalent instances of size at most $BigOh(4^k)$, a so-called kernelization. Since then the existence of a polynomial kernel for OCT, i.e., a kernelization with size bounded polynomially in $k$, 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 $k$. 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 $k$. The process is randomized with one-sided error exponentially small in $k$, 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 $BigOh(sqrtlogn)$-approximation (Agarwal et al., STOC 2005), we get a reduction of the instance to size $BigOh(k^{4.5})$, 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

(42)

• scientific article; zbMATH DE number 7765420 (Why is no real title available?)
• Odd cycle transversal on P₅-free graphs in polynomial time
• On polynomial kernels for structural parameterizations of odd cycle transversal
• An Updated Experimental Evaluation of Graph Bipartization Methods
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• Multi-budgeted directed cuts
• Multi-budgeted directed cuts
• Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
• Approximation and kernelization for chordal vertex deletion
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
• Kernelization -- preprocessing with a guarantee
• Representative sets and irrelevant vertices: new tools for kernelization
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• A survey of parameterized algorithms and the complexity of edge modification
• Exploiting dense structures in parameterized complexity
• Simpler parameterized algorithm for OCT
• Subexponential parameterized odd cycle transversal on planar graphs
• On Weighted Graph Separation Problems and Flow Augmentation
• On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
• A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• 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
• Preprocessing to reduce the search space for odd cycle transversal
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• Exploring the kernelization borders for hitting cycles
• A Compression Algorithm for Probability Transition Matrices
• Another disjoint compression algorithm for odd cycle transversal
• Proximity Search for Maximal Subgraph Enumeration
• Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• A constant-factor approximation for weighted bond cover
• On the kernelization complexity of problems on graphs without long odd cycles
• 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
• Edge bipartization faster than \(2^k\)
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
• Hitting selected (odd) cycles
• Odd multiway cut in directed acyclic graphs

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)