Search-space Reduction for Boolean MinCSPs via Essential Constraints

Bart M. P. Jansen, Ruben F. A. Verhaegh

For a fixed set $\mathcal{F}$ of Boolean constraint types, a MinCSP$(\mathcal{F})$-instance consists of a formula $F$ that applies $m$ constraints from $\mathcal{F}$ to a set of $n…