Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets

Serge Gaspers, Gregory B. Sorkin

We show a method resulting in the improvement of several polynomial-space, exponential-time algorithms. An instance of the problem Max (r,2)-CSP, or simply Max 2-CSP, is parametriz…