ECCC-Report TR00-037https://eccc.weizmann.ac.il/report/2000/037Comments and Revisions published for TR00-037en-usTue, 06 Jun 2000 18:28:45 +0300
Paper TR00-037
| New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT |
Jens Gramm,
Edward Hirsch,
Rolf Niedermeier,
Peter Rossmanith
https://eccc.weizmann.ac.il/report/2000/037The maximum 2-satisfiability problem (MAX-2-SAT) is:
given a Boolean formula in $2$-CNF, find a truth
assignment that satisfies the maximum possible number
of its clauses. MAX-2-SAT is MAXSNP-complete.
Recently, this problem received much attention in the
contexts of approximation (polynomial-time) algorithms
and exact (exponential-time) algorithms. In this paper,
we present an exact algorithm solving MAX-2-SAT in time
poly(L) 2^{K/5}, where K is the number of clauses and L
is their total length. Since, in our analysis, we count
only clauses containing exactly two literals, this
bound implies the bound poly(L) 2^{L/10}.
Our results significantly improve previous bounds:
poly(L) 2^{K/2.88} [Niedermeier, Rossmanith, 00] and
poly(L) 2^{K/3.44} (implicit in [Bansal, Raman, 99]).
Concerning the bound w.r.t. L, nothing better than the
bound poly(L) 2^{L/6.89} [Bansal, Raman, 99] for
(general) MAX-SAT was known. Our algorithm, together
with its analysis, is much simpler than recent MAX-SAT
algorithms (previous MAX-2-SAT bounds were obtained by
general MAX-SAT algorithms using inequalities relating
different input formula parameters).
As an application, we derive upper bounds for the
(MAXSNP-complete) maximum cut problem (MAX-CUT), showing
that it can be solved in time poly(M) 2^{M/3}, where M
is the number of edges in the given graph. This is of
special interest for graphs with low vertex degree.
Tue, 06 Jun 2000 18:28:45 +0300https://eccc.weizmann.ac.il/report/2000/037