On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal

The

Odd Cycle Transversal

problem (OCT) asks whether a given graph can be made bipartite (i.e., 2-colorable) by deleting at most ℓ vertices. We study structural parameterizations of OCT with respect to their polynomial kernelizability, i.e., whether instances can be efficiently reduced to a size polynomial in the chosen parameter. It is a major open problem in parameterized complexity whether

Odd Cycle Transversal

admits a polynomial kernel when parameterized by ℓ.

On the positive side, we show a polynomial kernel for OCT when parameterized by the vertex deletion distance to the class of bipartite graphs of treewidth at most

w

(for any constant

w

); this generalizes the parameter feedback vertex set number (i.e., the distance to a forest).

Complementing this, we exclude polynomial kernels for OCT parameterized by the distance to outerplanar graphs, conditioned on the assumption that NP

$\nsubseteq$

coNP/poly. Thus the bipartiteness requirement for the treewidth

w

graphs is necessary. Further lower bounds are given for parameterization by distance from cluster and co-cluster graphs respectively, as well as for

Weighted

OCT parameterized by the vertex cover number (i.e., the distance from an independent set).