Search-space Reduction for Boolean MinCSPs via Essential Constraints
Bart M. P. Jansen, Ruben F. A. Verhaegh · 2026
Read Search-space Reduction for Boolean MinCSPs via Essential Constraints by Bart M. P. Jansen, Ruben F. A. Verhaegh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00770.txt.
Description
Jansen and Verhaegh shrink the search space for a class of logic tasks in this 2026 paper. A Boolean MinCSP asks for the fewest rules to drop from a formula so the rest can be satisfied. Past work mapped how the rule set shapes how fast and how well this can be solved. A rule use counts as c-essential if every near-best fix must keep it.
Spotting such must-keep rules early cuts the space that later algorithms must search. The pair prove a dichotomy theorem on when this spotting can be done fast. For some rule sets it can. For others it is intractable, under standard beliefs in complexity theory. For all sets of bijunctive rules, they give a fast detector for such rules. This stands out, since near-best answers for those tasks are hard to approach even by a constant factor.
Catalog record
| CREATOR | Bart M. P. Jansen, Ruben F. A. Verhaegh |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 14 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.00770