A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

DOI10.1007/978-3-642-03816-7_28zbMath1250.68125OpenAlexW1498058293WikidataQ57359771 ScholiaQ57359771MaRDI QIDQ5895104

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

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

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

Related Items

Measuring Indifference: Unit Interval Vertex Deletion

Cites Work

• Finding odd cycle transversals.
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• Fixed-parameter algorithms for cluster vertex deletion
• Almost 2-SAT is fixed-parameter tractable
• 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.
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Obtaining a Planar Graph by Vertex Deletion
• Chordal Deletion Is Fixed-Parameter Tractable
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item