Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP

摘要: The class $(r,2)$-CSP, or simply Max 2-CSP, consists of constraint satisfaction problems with at most two $r$-valued variables per clause. For instances $n$ and $m$ binary clauses, we present an $O(n r^{5+19m/100})$-time algorithm which is the fastest polynomial-space for many in class, including Cut. method also proves a treewidth bound $\tw(G) \leq (13/75+o(1))m$, gives faster 2-CSP that uses exponential space: running time $\Ostar{2^{(13/75+o(1))m}}$, this 2-CSP. Parametrizing terms rather than $m$, graphs average degree $d$ show simple $\Ostar{2^{(1-\frac{2}{d+1})n}}$, known. In combination ``Polynomial CSPs'' introduced companion paper, these algorithms allow (with additional polynomial-factor overhead space time) counting sampling, solution like Bisection escape usual CSP framework. Linear programming key to design as well analysis algorithms.