Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover Original Research Article

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 image, improving the previous bound of image 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 image. Both inapproximability results apply to instances with no mixed clauses (the literals in every clause are both either negated, or unnegated).