Faster algorithm for Unique (k,2)-CSP
share
In a (k,2)-Constraint Satisfaction Problem we are given a set of arbitrary constraints on pairs of k-ary variables, and are asked to find an assignment of values to these variables such that all constraints are satisfied. The (k,2)-CSP problem generalizes problems like k-coloring and k-list-coloring. In the Unique (k,2)-CSP problem, we add the assumption that the input set of constraints has at most one satisfying assignment. Beigel and Eppstein gave an algorithm for (k,2)-CSP running in time O((0.4518k)^n) for k>3 and O(1.356^n) for k=3, where n is the number of variables. Feder and Motwani improved upon the Beigel-Eppstein algorithm for k≥ 11. Hertli, Hurbain, Millius, Moser, Scheder and Szedlák improved these bounds for Unique (k,2)-CSP for every k≥ 5. We improve the result of Hertli et al. and obtain better bounds for Unique (k,2)-CSP for k≥ 5. In particular, we improve the running time of Unique (5,2)-CSP from O(2.254^n) to O(2.232^n) and Unique (6,2)-CSP from O(2.652^n) to O(2.641^n).
READ FULL TEXT