On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
From MaRDI portal
Publication:2891343
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
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
