Wheel-Free Deletion Is W[2]-Hard

DOI10.1007/978-3-540-79723-4_14zbMath1142.68366OpenAlexW2163101585MaRDI QIDQ3503585

Daniel Lokshtanov

Publication date: 5 June 2008

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79723-4_14

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 (18)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Vertex deletion into bipartite permutation graphs ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Obtaining a planar graph by vertex deletion ⋮ Proper interval vertex deletion ⋮ Parameterized complexity of Eulerian deletion problems ⋮ Unnamed Item ⋮ Minimization and parameterized variants of vertex partition problems on graphs ⋮ Chordal deletion is fixed-parameter tractable ⋮ Vertex deletion into bipartite permutation graphs ⋮ Proper Interval Vertex Deletion ⋮ Parameterizing above or below guaranteed values ⋮ Parameterized Complexity of Vertex Deletion into Perfect Graph Classes ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Tractability of König edge deletion problems ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orienting graphs to optimize reachability
• Finding odd cycle transversals.
• Graph minors. XX: Wagner's conjecture
• Chordal completions of planar graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of finding subgraphs with hereditary properties.
• Graph minors. XIII: The disjoint paths problem
• On the Desirability of Acyclic Database Schemes
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Chordal Deletion Is Fixed-Parameter Tractable
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Complexity classification of some edge modification problems

This page was built for publication: Wheel-Free Deletion Is W[2]-Hard