On Approximation Hardness of the Minimum 2SAT-DELETION Problem

摘要

The MINIMUM 2SAT-DELETION problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems, and its approximability is largely open. We prove a lower approximation bound of 8(5~(1/2)) - 15 ≈ 2.88854, improving the previous bound of 10(5~(1/2))- 21 ≈ 1.36067 by Dinur and Safra. For highly restricted instances with exactly 4 occurrences of every variable we provide a lower bound of |. Both inapproximability results apply to instances with no mixed clauses (the literals in every clause are both either negated, or unnegated). We further prove that any k-approximation algorithm for MINIMUM 2SAT-DELETION polynomially reduces to a (2 - 2/(k+1)-approximation algorithm for the MINIMUM VERTEX COVER problem. One ingredient of these improvements is our proof that for the MINIMUM VERTEX COVER problem restricted to graphs with a perfect matching its threshold on polynomial time approximability is the same as for the general MINIMUM VERTEX COVER problem. This improves also on results of Chen and Kanj.