On approximation hardness of the Minimum 2SAT-DELETION problem

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

103 Downloads (Pure)

Abstract

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 - 15 ≈ 2:88854, improving the previous bound of 10√5 - 21 ≈ 1:36067 by Dinur and Safra. For highly restricted instances with exactly 4 occurrences of every variable we provide a lower bound of 3/2 . Both in approximability 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 poly nomially 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.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2004
Subtitle of host publication29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings
EditorsJiri Fiala, Vaclav Koubek, Jan Kratochvil
Place of PublicationCham
PublisherSpringer
Chapter18
Pages263-273
Number of pages11
ISBN (Electronic)9783540286295
ISBN (Print)9783540228233
DOIs
Publication statusPublished - 2004
Event29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004) - Prague, Czech Republic
Duration: 22 Aug 200427 Aug 2004

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3153
ISSN (Print)0302-9743

Conference

Conference29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004)
Country/TerritoryCzech Republic
CityPrague
Period22/08/0427/08/04

Fingerprint

Dive into the research topics of 'On approximation hardness of the Minimum 2SAT-DELETION problem'. Together they form a unique fingerprint.

Cite this