Parameterized complexity of vertex deletion into perfect graph classes

DOI10.1016/J.TCS.2012.03.013zbMath1407.68223OpenAlexW2054901865MaRDI QIDQ392038

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

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.013

zbMATH Keywords

perfect graphsparameterized complexitykernelizationvertex deletion problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Perfect graphs (05C17)

Related Items (18)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Vertex deletion into bipartite permutation graphs ⋮ Structural parameterizations with modulator oblivion ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ Quadratic vertex kernel for split vertex deletion ⋮ Vertex deletion into bipartite permutation graphs ⋮ Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques ⋮ A completeness theory for polynomial (Turing) kernelization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• 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
• On problems without polynomial kernels
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of finding subgraphs with hereditary properties.
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• Obtaining a planar graph by vertex deletion
• A 4 k ² kernel for feedback vertex set
• Isomorphism for Graphs of Bounded Feedback Vertex Set Number
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Incompressibility through Colors and IDs
• Graph Classes: A Survey

This page was built for publication: Parameterized complexity of vertex deletion into perfect graph classes