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

CREATORBart M. P. Jansen, Ruben F. A. Verhaegh
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.00770

Browse the full library · About the Tower of Babel