Maximum Exact Satisfiability: NP-completeness Proofs and Exact Algorithms

Bolette Ammitzbøll Madsen
Peter Rossmanith

October 2004

Abstract:

Inspired by the Maximum Satisfiability and Exact Satisfiability problems we present two Maximum Exact Satisfiability problems. The first problem called Maximum Exact Satisfiability is: given a formula in conjunctive normal form and an integer $k$, is there an assignment to all variables in the formula such that at least $k$ clauses have exactly one true literal. The second problem called Restricted Maximum Exact Satisfiability has the further restriction that no clause is allowed to have more than one true literal. Both problems are proved NP-complete restricted to the versions where each clause contains at most two literals. In fact Maximum Exact Satisfiability is a generalisation of the well-known NP-complete problem MaxCut. We present an exact algorithm for Maximum Exact Satisfiability where each clause contains at most two literals with time complexity $O(poly(L) \cdot 2^{m/4})$, where $m$ is the number of clauses and $L$ is the length of the formula. For the second version we give an algorithm with time complexity $O(poly(L) \cdot 1.324718^n)$, where $n$ is the number of variables. We note that when restricted to the versions where each clause contains exactly two literals and there are no negations both problems are fixed parameter tractable. It is an open question if this is also the case for the general problems.

Available as PostScript, PDF.

Last modified: 2004-10-13 by webmaster.