1 <scp>-in-</scp> 3 <scp>vs</scp> . N <scp>ot</scp> -A <scp>ll</scp> -E <scp>qual</scp> : Dichotomy of a Broken Promise
The 1 -in- 3 and N ot -A ll -E qual satisfiability problems for Boolean CNF formulas are two well-known NP -hard problems. In contrast, the promise 1 -in- 3 vs . N ot -A ll -E qual problem can be solved in polynomial time. In the present work, we investigate this constraint satisfaction problem in a regime where the promise is weakened from either side by a rainbow-free structure and establish a complexity dichotomy for the resulting class of computational problems.
Authors
- Andrei Krokhin (ORCID: https://orcid.org/0000-0003-4373-8227)
- Marcin Kozik (ORCID: https://orcid.org/0000-0002-1839-4824)
- Stanislav Živný (ORCID: https://orcid.org/0000-0002-0263-159X)
- Tamio-Vesa Nakajima (ORCID: https://orcid.org/0000-0003-3684-9412)
- Lorenzo Ciardo (ORCID: https://orcid.org/0000-0001-9491-2016)
Institutions
- Jagiellonian University (PL)
- Universities UK (GB)
- Durham University (GB)
- University of Oxford (GB)
Publication Details
- Journal
- ACM Transactions on Computational Logic
- Published
- 2025-02-20
- DOI
- https://doi.org/10.1145/3719007
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00