License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.92
URN: urn:nbn:de:0030-drops-170309
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17030/
Go to the corresponding LIPIcs Volume Portal

Zamir, Or

Faster Algorithm for Unique (k,2)-CSP

pdf-format:
LIPIcs-ESA-2022-92.pdf (0.6 MB)

Abstract

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ⁿ) 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ⁿ) 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:1--92:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17030},
  URN =		{urn:nbn:de:0030-drops-170309},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI