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

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 Khanna et al. [Constraint satisfaction: the approximability of minimization problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany, 24-27 June, 1997, pp. 282-296], and its approximability is largely open. We prove a lower approximation bound of 8 root 5-15 approximate to 2.88854, improving the previous bound of 10 root 5-21 approximate to 1.36067 by Dinur and Safra [The importance of being biased, Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), May 2002, pp. 33-42, also ECCC Report TR01-104, 2001]. For highly restricted instances with exactly four occurrences of every variable we provide a lower bound of 3/2. 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 the MINIMUM 2SAT-DELETION problem 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 the MINIMUM VERTEX COVER problem is hardest to approximate on graphs with perfect matching. More precisely, the problem to design a p-approximation algorithm for the MINIMUM VERTEX COVER on general graphs polynomially reduces to the same problem on graphs with perfect matching. This improves also on the results by Chen and Kanj [On approximating minimum vertex cover for graphs with perfect matching, Proceedings of the 11st ISAAC, Taipei, Taiwan, Lecture Notes in Computer Science, vol. 1969, Springer, Berlin, 2000, pp. 132-143]. (c) 2006 Elsevier B.V. All rights reserved.