Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal

Details Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal

2011-07-15

arxiv.org/abs/1107.3068v2

Computer Science

Data Structures and Algorithms

Minor changes to agree with SODA 2012 version of the paper

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-226391