{"ID":2922121,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-02T15:14:47.885127409Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.00770","arxiv_id":"2606.00770","title":"Search-space Reduction for Boolean MinCSPs via Essential Constraints","abstract":"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$ Boolean variables. The goal is to remove a minimum subset of constraint applications from $F$ to make the remaining formula satisfiable. Previous work characterized how the choice of $\\mathcal{F}$ affects its polynomial-time solvability and approximability. We extend a recently introduced preprocessing framework for graph problems to the problem above. Rephrased in the context of CSPs, this framework defines a constraint application from a given formula $F$ as $c$-essential if it is contained in all $c$-approximate solutions to $F$. Being able to efficiently detect these essential parts of a solution reduces the search space of any follow-up FPT algorithms parameterized by the solution size and yields an immediate asymptotic improvement to the runtime of such algorithms. In this work, we present a dichotomy theorem that distinguishes constraint sets $\\mathcal{F}$ for which $c_\\mathcal{F}$-essential constraint applications can be detected efficiently for some $c_{\\mathcal{F}} \\in \\mathcal{O}(1)$, from those for which this task is intractable under established complexity-theoretic conjectures. Our results show that for any set $\\mathcal{F}$ of bijunctive constraints, there is a polynomial-time algorithm that detects $\\mathcal{O}(1)$-essential constraint applications. This contrasts the fact that constant-factor approximating a bijunctive MinCSP$(\\mathcal{F})$-problem is intractable under the Unique Games Conjecture.","short_abstract":"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$ Boolean variables. The goal is to remove a minimum subset of constraint applications from $F$ to make the remaining formula satisfiable. P...","url_abs":"https://arxiv.org/abs/2606.00770","url_pdf":"https://arxiv.org/pdf/2606.00770v1","authors":"[\"Bart M. P. Jansen\",\"Ruben F. A. Verhaegh\"]","published":"2026-05-30T15:21:37Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}