A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

DOI10.1007/978-3-642-03816-7_28MaRDI QIDQ5895104zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03816-7_28

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A complexity dichotomy for finding disjoint solutions of vertex deletion problems
• Complexity of disjoint -vertex deletion for disconnected forbidden subgraphs
• Complexity of disjoint \({\Pi}\)-vertex deletion for disconnected forbidden subgraphs
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Iterative compression and exact algorithms

Cites work

• A fixed-parameter algorithm for the directed feedback vertex set problem
• Almost 2-SAT is fixed-parameter tractable
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Chordal Deletion Is Fixed-Parameter Tractable
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Finding odd cycle transversals.
• Fixed-parameter algorithms for cluster vertex deletion
• Fixed-parameter tractability of graph modification problems for hereditary properties
• scientific article; zbMATH DE number 2086259 (Why is no real title available?)
• scientific article; zbMATH DE number 3487498 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved algorithms for feedback vertex set problems
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Obtaining a Planar Graph by Vertex Deletion
• Parameterized complexity of finding subgraphs with hereditary properties.
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(12)

• On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
• On the complexity of singly connected vertex deletion
• Iterative compression and exact algorithms
• Complexity of disjoint \({\Pi}\)-vertex deletion for disconnected forbidden subgraphs
• Measuring indifference: unit interval vertex deletion
• Iterative Compression and Exact Algorithms
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• scientific article; zbMATH DE number 7278081 (Why is no real title available?)
• Combining the Delete Relaxation with Critical-Path Heuristics: A Direct Characterization
• Complexity of disjoint -vertex deletion for disconnected forbidden subgraphs
• A complexity dichotomy for finding disjoint solutions of vertex deletion problems
• Vertex deletion on split graphs: beyond 4-hitting set

This page was built for publication: A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895104)