University of Sussex
Browse

File(s) not publicly available

On approximation hardness of the minimum 2SAT-deletion problem

presentation
posted on 2023-06-07, 22:04 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
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 [8], and its approximability is largely open. We prove a lower approximation bound of 8root5 - 15 approximate to 2.88854, improving the previous bound of 10root5 - 21 approximate to 1.36067 by Dinur and Safra [5]. For highly restricted instances with exactly 4 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 MINIMUM 2SAT-DELETION 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 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 [3].

History

Publication status

  • Published

ISSN

0302-9743

Publisher

Springer Berlin / Heidelberg

Volume

LNCS 3

Page range

263-273

Presentation Type

  • paper

Event name

29th International Symposium on Mathematical Foundations of Computer Science

Event location

Prague, CZECH REPUBLIC

Event type

conference

ISBN

978-3-540-22823-3

Department affiliated with

  • Mathematics Publications

Notes

Mathematical Foundations of Computer Science 2004

Full text available

  • No

Peer reviewed?

  • Yes

Editors

J Kratochvil, J Fiala, V Koubek

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC