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

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

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 |