TR00-037 Authors: Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith

Publication: 6th June 2000 18:28

Downloads: 1467

Keywords:

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