Solving MAX-r-SAT Above a Tight Lower Bound

Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider and Anders Yeo

Algorithmica, vol. 61, no. 3, 2011, pp. 638-655.

A preliminary version appeared in the proceedings of SODA 2010, the Twenty-First ACM-SIAM Symposium on Discrete Algorithms, pp. 511-517, SIAM, 2010.

Abstract:

We present an exact algorithm that decides in time m^O(1) + 2^O(k²) whether a given multiset of m clauses of size r admits a truth assignment that satisfies at least (3m+k)/4 clauses. Thus MAX-r-SAT is fixed-parameter tractable when parameterized above the tight lower bound (1-2^-r)m. Our algorithm is based on probabilistic arguments and a polynomial-time procedure that reduces a problem instance to an equivalent algebraically represented problem with O(k²) variables. This solves and open problem of Mahajan, Raman and Sikdar (J. Comput. System Sci., 75, 2009). Using tools from graph matching theory and signed graphs, we give an improved algorithm for the case r=2. We also outline how the fixed-parameter tractability result on MAX-r-SAT can be extended to a family of Boolean Constraint Satisfaction Problems.