Computer Science – Data Structures and Algorithms
Scientific paper
2011-07-19
Computer Science
Data Structures and Algorithms
Accepted to IPEC 2011, Saarbrucken
Scientific paper
The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite (i.e., 2-colorable) by deleting at most l 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 l. 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 \not \subseteq 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).
Jansen Bart M. P.
Kratsch Stefan
No associations
LandOfFree
On Polynomial Kernels for Structural Parameterizations of 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 On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-514339