Parameterized Complexity of Vertex Deletion into Perfect Graph Classes

DOI10.1007/978-3-642-22953-4_21zbMath1342.68165OpenAlexW32464776MaRDI QIDQ3088287

Stefan Kratsch, Bart M. P. Jansen, Pim van 't Hof, Yngve Villanger, Pinar Heggernes

Publication date: 19 August 2011

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22953-4_21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Paths to Trees and Cacti ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Proper interval vertex deletion ⋮ Contracting graphs to paths and trees ⋮ Paths to trees and cacti ⋮ Modifying a graph using vertex elimination ⋮ Faster parameterized algorithms for deletion to split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Improved upper bounds for vertex cover
• The strong perfect graph theorem
• A cubic kernel for feedback vertex set and loop cutset
• Chordal deletion is fixed-parameter tractable
• A kernelization algorithm for \(d\)-hitting set
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Algorithmic graph theory and perfect graphs
• Wheel-Free Deletion Is W[2-Hard]
• Obtaining a Planar Graph by Vertex Deletion
• On Problems without Polynomial Kernels (Extended Abstract)
• Isomorphism for Graphs of Bounded Feedback Vertex Set Number
• A Problem Kernelization for Graph Packing
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Graph Classes: A Survey
• (Meta) Kernelization

This page was built for publication: Parameterized Complexity of Vertex Deletion into Perfect Graph Classes