On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal

DOI10.1007/978-3-642-28050-4_11zbMath1352.68112arXiv1107.3658OpenAlexW1546304675MaRDI QIDQ2891343

Bart M. P. Jansen, Stefan Kratsch

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1107.3658

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ On structural parameterizations for the 2-club problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infeasibility of instance compression and succinct PCPs for NP
• Finding odd cycle transversals.
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Parameterized graph separation problems
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• On problems without polynomial kernels
• Linear time solvable optimization problems on graphs of bounded clique-width
• Planar graph bipartization in linear time
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Treewidth reduction for constrained separation and bipartization problems
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Two-Layer Planarization Parameterized by Feedback Edge Set
• On the power of unique 2-prover 1-round games
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Algorithm Engineering for Optimal Graph Bipartization
• Compression via Matroids
• (Meta) Kernelization
• Theoretical Computer Science
• Multicut is FPT
• Fixed-parameter tractability of multicut parameterized by the size of the cutset