On approximation hardness of the Minimum 2SAT-DELETION problem

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/978-3-540-28629-5_18

On approximation hardness of the Minimum 2SAT-DELETION problem

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

184 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 language	English
Title of host publication	Mathematical Foundations of Computer Science 2004
Subtitle of host publication	29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings
Editors	Jiri Fiala, Vaclav Koubek, Jan Kratochvil
Place of Publication	Cham
Publisher	Springer
Chapter	18
Pages	263-273
Number of pages	11
ISBN (Electronic)	9783540286295
ISBN (Print)	9783540228233
DOIs	https://doi.org/10.1007/978-3-540-28629-5_18
Publication status	Published - 2004
Event	29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004) - Prague, Czech Republic Duration: 22 Aug 2004 → 27 Aug 2004

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	3153
ISSN (Print)	0302-9743

Conference

Conference	29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004)
Country/Territory	Czech Republic
City	Prague
Period	22/08/04 → 27/08/04

Access to Document

10.1007/978-3-540-28629-5_18

Approximation Hardness post-print
The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-540-28629-5_18.
Accepted author manuscript (Post-print), 187 KB

Cite this

Chlebik, M., & Chlebikova, J. (2004). On approximation hardness of the Minimum 2SAT-DELETION problem. In J. Fiala, V. Koubek, & J. Kratochvil (Eds.), Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings (pp. 263-273). (Lecture Notes in Computer Science; Vol. 3153). Springer. https://doi.org/10.1007/978-3-540-28629-5_18

Chlebik, Miroslav ; Chlebikova, Janka. / On approximation hardness of the Minimum 2SAT-DELETION problem. Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings. editor / Jiri Fiala ; Vaclav Koubek ; Jan Kratochvil. Cham : Springer, 2004. pp. 263-273 (Lecture Notes in Computer Science).

@inproceedings{767561a297f94a12bd07c7c220d57daf,

title = "On approximation hardness of the Minimum 2SAT-DELETION problem",

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.",

author = "Miroslav Chlebik and Janka Chlebikova",

year = "2004",

doi = "10.1007/978-3-540-28629-5_18",

language = "English",

isbn = "9783540228233",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "263--273",

editor = "Jiri Fiala and Vaclav Koubek and Jan Kratochvil",

booktitle = "Mathematical Foundations of Computer Science 2004",

note = "29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004) ; Conference date: 22-08-2004 Through 27-08-2004",

}

Chlebik, M & Chlebikova, J 2004, On approximation hardness of the Minimum 2SAT-DELETION problem. in J Fiala, V Koubek & J Kratochvil (eds), Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings. Lecture Notes in Computer Science, vol. 3153, Springer, Cham, pp. 263-273, 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), Prague, Czech Republic, 22/08/04. https://doi.org/10.1007/978-3-540-28629-5_18

On approximation hardness of the Minimum 2SAT-DELETION problem. / Chlebik, Miroslav; Chlebikova, Janka.
Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings. ed. / Jiri Fiala; Vaclav Koubek; Jan Kratochvil. Cham: Springer, 2004. p. 263-273 (Lecture Notes in Computer Science; Vol. 3153).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On approximation hardness of the Minimum 2SAT-DELETION problem

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-28629-5_18

DO - 10.1007/978-3-540-28629-5_18

M3 - Conference contribution

SN - 9783540228233

T3 - Lecture Notes in Computer Science

SP - 263

EP - 273

BT - Mathematical Foundations of Computer Science 2004

A2 - Fiala, Jiri

A2 - Koubek, Vaclav

A2 - Kratochvil, Jan

PB - Springer

CY - Cham

T2 - 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004)

Y2 - 22 August 2004 through 27 August 2004

ER -

Chlebik M, Chlebikova J. On approximation hardness of the Minimum 2SAT-DELETION problem. In Fiala J, Koubek V, Kratochvil J, editors, Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings. Cham: Springer. 2004. p. 263-273. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-28629-5_18

On approximation hardness of the Minimum 2SAT-DELETION problem

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this