New exact algorithms for the 2-constraint satisfaction problem

Many optimization problems can be phrased in terms of constraint satisfaction. In particular MAX-2-SAT and MAX-2-CSP are known to generalize many hard combinatorial problems on graphs. Algorithms solving the problem exactly have been designed but the running time is improved over trivial brute-force solutions only for very sparse instances. Despite many efforts, the only known algorithm [28] solving MAX-2-CSP over n   variables in less than O⁎(2n)O⁎(2n) steps uses exponential space.Several authors have designed algorithms with running time O⁎(2nf(d))O⁎(2nf(d)) where f:R+→(0,1)f:R+→(0,1) is a slowly growing function and d is the average variable degree of the input formula. The current best known algorithm for MAX-2-CSP [25] runs in time O⁎(2n(1−2d+1)) and polynomial space. In this paper we continue this line of research and design new algorithms for the MAX-2-SAT and MAX-2-CSP problems.First, we present a general technique for obtaining new bounds on the running time of a simple algorithm for MAX-2-CSP analyzed with respect to the number of vertices from algorithms that are analyzed with respect to the number of constraints. The best known bound for the problem is improved to O⁎(2n(1−3d+1)) for d⩾3d⩾3. We further improve the bound for MAX-2-SAT, in particular for d⩾6d⩾6 we achieve O⁎(2n(1−3.677d+1)).As a second result we present an algorithm with asymptotically better running time for the case when the input instance is not very sparse. Building on recent work of Feige and Kogan we derive an upper bound on the size of a vertex separator for graphs in terms of the average degree of the graph. We then design a simple algorithm solving MAX-2-CSP in time O⁎(2cdn)O⁎(2cdn), cd=1−2αlndd for some α<1α<1 and d=o(n)d=o(n).