Approximation Algorithms for Minimum Chain Vertex Deletion

DOI10.1007/978-3-642-19094-0_5zbMath1317.68281MaRDI QIDQ3078376

Sounaka Mishra, N. Safina Devi, Saket Saurabh, Mrinal Kumar

Publication date: 20 February 2011

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19094-0_5

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating the Minimum Chain Completion problem
• The node-deletion problem for hereditary properties is NP-complete
• Optimization, approximation, and complexity classes
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Node-Deletion Problems on Bipartite Graphs
• Computing the Minimum Fill-In is NP-Complete
• On the hardness of approximating minimization problems
• Interactive proofs and the hardness of approximating cliques
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem