Source-linked AI summary
Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal
Stefan Kratsch, Magnus Wahlström
TL;DR
Whether OCT admits a polynomial kernel remained an important open question. This paper uses matroid representations to encode information for a randomized compression, obtaining an O(k^4.5)-size OCT result with one-sided error.
Problem
Whether Odd Cycle Transversal admits a polynomial kernel remained open, including for planar graphs.
Source: §1 · p. 2Method
Results
O(k^4.5) randomized compression for OCT has one-sided error, with no false negatives and failure probability exponentially small in k.
Source: §4.2 · p. 10Takeaways & Limitations
The work introduces matroid theory as a kernelization tool with potential use in future kernelization results.
Source: §1 · p. 4A deterministic polynomial kernelization remains open, and the correct size bound is unresolved.
Source: §5 · p. 11
Abstract
from arXiv · showhide
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^kkmn)$ 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(\sqrt{\log n})$-approximation (Agarwal et al., STOC 2005), we get a reduction of the instance to size $\BigOh(k^{4.5})$, implying a randomized polynomial kernelization.
1 Introduction
Polynomial kernels are a major open question for OCT, which asks whether deleting at most k vertices can make a graph bipartite. This work introduces a randomized matroid-based approach and obtains a polynomial-size compression for OCT.
Introduction
- A polynomial kernel formalizes efficient data reduction and is regarded as a significant threshold in parameterized complexity.The introduction frames OCT’s open kernel question against this broader importance.Source: §1 · p. 2
Related work
- Polynomial kernels for OCT and Directed Feedback Vertex Set remained open questions, including for planar graphs.OCT asks whether deleting at most k vertices makes a graph bipartite.Source: §1 · p. 2
What makes OCT special?
- OCT lacks the structural features or useful exceptions that support many polynomial kernels for graph-modification problems.The introduction also notes that known sparse-input meta-results do not cover OCT, even on planar inputs.Source: §1 · p. 3
Our work
- The matroid encodes information needed to simulate Reed, Smith, and Vetta’s iterative-compression step, using an initial approximate solution as terminals.A gammoid-based matrix has total size cubic in the number of terminals and logarithmic in the graph size.Source: §1 · p. 3
- For unrestricted OCT, combining iterative compression with gammoid-based matroid simulation and the O(√log n)-approximation yields an O(k^4.5)-size randomized polynomial compression, completing the kernelization.Source: §1 · pp. 3–4
2 Preliminaries
The preliminaries define kernelization and randomized one-sided-error variants, then introduce matroids and their linear representations. These definitions establish the compression framework and representation tools used in the paper.
2.1 Parameterized complexity and kernelization
- A kernelization maps an instance in polynomial time to an equivalent instance whose size and parameter are bounded by a function of the original parameter.It is polynomial when that size bound is polynomially bounded.Source: §2.1 · p. 4
- A polynomial compression may map to a different language, and when that language is in NP, it implies a polynomial kernelization under the stated completeness condition [11].The paper defines a coRP-kernelization as a randomized kernelization without false negatives.Source: §2.1 · pp. 4–5
- Combining outputs from independent runs can form a joint compression, since majority or simple conjunction over separate kernelization outputs cannot boost success probability.The paper notes this joint output can be converted back into a kernelization.Source: §2.1 · p. 5
2.2 Matroids
- A matroid consists of a ground set and independent sets satisfying heredity and the exchange property; a matrix represents one when its independent column sets define its independence.The paper focuses on linear matroids, representable over a field.Source: §2.2 · p. 5
- Matroid minors arise through deletions and contractions, and both operations preserve a representation.Contraction is defined via the dual matroid.Source: §2.2 · pp. 5–6
3 Polynomial encoding of terminal cuts using gammoids
This section encodes terminal-cut information using gammoids and linear matroid representations. The resulting randomized matrices preserve linkage information with one-sided error and polynomially bounded representation size.
3 Polynomial encoding of terminal cuts using gammoids
- Direct graph simplification preserving every terminal cut appears difficult, so the section uses matroid representations to encode the required cut information.The target is polynomial size in the number of terminals and log |V|, while preserving minimum cut sizes for terminal pairs and allowing specified terminals to be removed.Source: §3 · p. 6
- Gammoids encode sets linked to fixed sources as matroid-independent sets [53, 46], turning vertex-disjoint linkage questions into linear-independence tests.Linked sets are those reachable by vertex-disjoint paths with disjoint endpoints.Source: §3 · p. 6
- A gammoid representation uses an |S| × |T| rational matrix with entry bit length O(min(|T|, |S| log |T|) + log(1/ε) + log |V|), with one-sided error at most ε.The representation can be computed in randomized polynomial time.Source: §3 · p. 6
- A constructed digraph translates terminal inclusion and deletion choices into gammoid independent sets exactly when the corresponding terminal path packings exist.The proof establishes both directions by converting independent sets to disjoint paths and path packings back to independent sets.Source: §3 · p. 7
- A randomized |X| × 2|X| integer matrix represents terminal linkage with probability at least 1−ε, and its indicated disjoint-path count is a lower bound on the true value.The entry bit length is O(|X|+log |V|+log 1/ε).Source: §3 · p. 8
4 A randomized polynomial kernel for odd cycle transversal
The paper combines iterative compression with matroid representations to obtain randomized polynomial compressions for OCT and related problems. The OCT compression has size O(k^4.5), with one-sided error and no false negatives.
4.1 The Reed-Smith-Vetta algorithm
- The Reed-Smith-Vetta routine turns a size-(k+1) bipartization set into cut queries in a bipartite graph G′, enumerating 3^|X| valid choices.It recursively solves G−v first; Lemma 1 expresses the optimum deletion size as |X\U| plus a minimum cut over valid splits.Source: §4.1 · p. 8
4.2 Kernelization
- The matrix coding size is cubic in |X|; with |X| bounded by O(k^1.5), the resulting OCT compression has size O(k^4.5).The construction uses the approximation-based bound on |X| before applying the compression.Source: §4.2 · p. 9
- O(|X|^2(|X| + log(1/ε))) size, error probability at most ε, and no false negatives are guaranteed by the randomized compression lemma.Its running time is polynomial in |G| and log(1/ε).Source: §4.2 · p. 10
- Matroid-representation independence tests replace the terminal-cut queries required by Lemma 1, using choices of U, valid splits, and removed terminals.The compression procedure first constructs an auxiliary graph G′ with terminal set X′, then uses a matrix to test the corresponding independence sets.Source: §4.2 · pp. 9–10
- O(k^4.5)-compression for OCT and randomized O~(k^3)-compression for Edge Bipartization have one-sided error, no false negatives, and failure probability exponentially small in k.These are the bounds stated in Theorem 2.Source: §4.2 · p. 10
- Odd Cycle Transversal, Edge Bipartization, Balanced Subgraph, and Tanglegram Layout have polynomial coRP-kernelizations.The result follows from the compression and the stated NP-completeness reductions.Source: §4.2 · p. 10
4.3 A Note on Lower Bounds
- No co-nondeterministic OCT compression of size O(k^(2−ε)) exists unless NP ⊆ coNP/poly and the polynomial hierarchy collapses.The authors say their methods appear difficult to improve below O(k^3), leaving improvement of either bound open.Source: §4.3 · p. 11
5 Conclusion
The paper presents randomized polynomial kernelizations for Odd Cycle Transversal and Edge Bipartization using matroids to encode the Reed-Smith-Vetta compression step. It leaves deterministic kernelizations and the correct size bounds open.
5 Conclusion
- O(k^4.5) for Odd Cycle Transversal and ˜O(k^3) for Edge Bipartization are achieved by matroid-based compression, then back-reductions to the original problems.The one-sided-error kernelization produces no false negatives, and its failure rate can be made exponentially small in k at only a constant-factor cost to size.Source: §5 · p. 11
- The method does not avoid the lower bounds of Fortnow and Santhanam; it settles problems lacking known lower bounds or polynomial kernels or compressions.Source: §5 · p. 11
- Whether deterministic polynomial kernelizations exist and what the correct size bounds are remain open for both problems.An O(polylog(OPT))-approximation for OCT would improve the result to ˜O(k^3), while a gap remains to the O(k^(2−ε)) lower bound.Source: §5 · p. 11