Optimal 2-constraint satisfaction via sum–product algorithms

We show that for a given set of m pairwise constraints over n variables, a variable assignment that satisfies maximally many m constraints (MAX-2-CSP) can be found in time, where d is the maximum number of states per variable, and ω<2.376 is the matrix product exponent over a ring; the notation O∗ suppresses factors polylogarithmic in m and n. As a corollary, MAX-2-SAT can be solved in O∗(nmn1.732) time. This improves on a recent result by Williams [R. Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoret. Comput. Sci. 348 (2–3) (2005) 357–365] by reducing the polynomial factor from nm3 to about nm.