2021/10/07 by Or Zamir, Zamir, Or
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2110.03122
openalex publication_date 2021/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.356n) 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.254n) to~O(2.232n) and Unique~(6,2)-CSP from~O(2.652n) to~O(2.641n).