On polynomial kernels for structural parameterizations of odd cycle transversal
From MaRDI portal
Abstract: 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
ot 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).
Recommendations
Cites work
- (Meta) Kernelization
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
- \textsc{Multicut} is FPT
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Algorithm Engineering for Optimal Graph Bipartization
- Compression via Matroids
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Cross-composition: a new technique for kernelization lower bounds
- Finding odd cycle transversals.
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Hitting forbidden minors: approximation and kernelization
- scientific article; zbMATH DE number 1945152 (Why is no real title available?)
- scientific article; zbMATH DE number 6297714 (Why is no real title available?)
- Infeasibility of instance compression and succinct PCPs for NP
- Linear time solvable optimization problems on graphs of bounded clique-width
- On problems without polynomial kernels
- On the power of unique 2-prover 1-round games
- Parameterized graph separation problems
- Planar graph bipartization in linear time
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Theoretical Computer Science
- Treewidth reduction for constrained separation and bipartization problems
- Two-layer planarization parameterized by feedback edge set
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
Cited in
(10)- On the kernelization complexity of problems on graphs without long odd cycles
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Parameterized algorithms for even cycle transversal
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Kernelization dichotomies for hitting subgraphs under structural parameterizations
- Bipartizing (pseudo-)disk graphs: approximation with a ratio better than 3
- Odd cycle transversal on P₅-free graphs in polynomial time
- Preprocessing complexity for some graph problems parameterized by structural parameters
- The parameter report: an orientation guide for data-driven parameterization
This page was built for publication: On polynomial kernels for structural parameterizations of odd cycle transversal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891343)
