Limit Behavior of Locally Consistent Constraint Satisfaction Problems
Manuel Bodirsky, Daniel Král͏̌ · SIAM Journal on Discrete Mathematics · 2011
An instance of a constraint satisfaction problem (CSP) is variable [Formula: see text]- consistent if any subinstance with at most [Formula: see text] variables has a solution. For a fixed constraint language [Formula: see text], [Formula: see text] is the largest ratio such that any variable [Formula: see text]-consistent instance has a solution that satisfies at least a fraction of [Formula: see text] of the constraints. We provide an expression for the limit [Formula: see text], and show that this limit coincides with the corresponding limit for constraint [Formula: see text]- consistent instances, i.e., instances where all subinstances with at most [Formula: see text] constraints have a solution. We also design an algorithm running in time polynomial in the size of input and [Formula: see text] that for an input instance and a given [Formula: see text] either computes a solution that satisfies at least a fraction of [Formula: see text] constraints or finds a set of inconsistent constraints whose size depends only on [Formula: see text]. Most of our results apply both to weighted and to unweighted instances of the CSP.