Abstract
In a (k,2)Constraint Satisfaction Problem we are given a set of arbitrary constraints on pairs of kary 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 kcoloring and klistcoloring. 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ⁿ) for k = 3, where n is the number of variables. Feder and Motwani improved upon the BeigelEppstein 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ⁿ) to O (2.232^n) and Unique (6,2)CSP from O (2.652^n) to O (2.641^n).
Recently, Li and Scheder also published an improvement over the algorithm of Hertli et al. in the same regime as ours. Their improvement does not include quantitative bounds, we compare the works in the paper.
BibTeX  Entry
@InProceedings{zamir:LIPIcs.ESA.2022.92,
author = {Zamir, Or},
title = {{Faster Algorithm for Unique (k,2)CSP}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {92:192:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17030},
URN = {urn:nbn:de:0030drops170309},
doi = {10.4230/LIPIcs.ESA.2022.92},
annote = {Keywords: Algorithms, Constraint Satisfaction Problem}
}
Keywords: 

Algorithms, Constraint Satisfaction Problem 
Collection: 

30th Annual European Symposium on Algorithms (ESA 2022) 
Issue Date: 

2022 
Date of publication: 

01.09.2022 