2012 | OriginalPaper | Chapter
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
Authors : Bart M. P. Jansen, Stefan Kratsch
Published in: Parameterized and Exact Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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).