2026-09-23T23:47:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26058 2026-09-05T19:35:59Z ddc:004 open_access

Search-Space Reduction for Boolean MinCSPs via Essential Constraints Jansen, Bart M. P. Verhaegh, Ruben F. A. fixed-parameter tractability constraint satisfaction problems For a fixed set ℱ of Boolean constraint types, a MinCSP(ℱ)-instance consists of a formula F that applies m constraints from ℱ 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 ℱ 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 ℱ for which c_ℱ-essential constraint applications can be detected efficiently for some c_{ℱ} ∈ 𝒪(1), from those for which this task is intractable under established complexity-theoretic conjectures. Our results show that for any set ℱ of bijunctive constraints, there is a polynomial-time algorithm that detects 𝒪(1)-essential constraint applications. This contrasts the fact that constant-factor approximating a bijunctive MinCSP(ℱ)-problem is intractable under the Unique Games Conjecture. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bart M. P. Jansen and Ruben F. A. Verhaegh 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.22 urn:nbn:de:0030-drops-260586 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.22 eng https://creativecommons.org/licenses/by/4.0/legalcode