Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover

DOI10.1016/j.dam.2006.04.039zbMath1110.68169OpenAlexW1972203976MaRDI QIDQ867859

Janka Chlebíková, Miroslav Chlebík

Publication date: 19 February 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.039

zbMATH Keywords

vertex coverapproximation hardness\(k\)-approximation algorithm2SAT-deletion

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (6)

On approximability of optimization problems related to red/blue-split graphs ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas ⋮ The complexity of König subgraph problems and above-guarantee vertex cover ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Popularity, Mixed Matchings, and Self-Duality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Complexity of approximating bounded variants of optimization problems
• Approximation Algorithms for Steiner and Directed Multicuts
• The importance of being biased
• Vertex packings: Structural properties and algorithms
• Some optimal inapproximability results
• Automata, Languages and Programming

This page was built for publication: Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover