An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems

摘要

An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set Π of constraint types, ρ_l(Π) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints from the set Π. We study the asymptotic behavior of ρ_l(Π) for sets Π consisting of Boolean predicates. The value ρ_∞(Π) := lim_(l → ∞) ρ_l(Π) is determined for all such sets Π. Moreover, we design a robust deterministic algorithm (for a fixed set Π of predicates) running in time linear in the size of the input and 1/ε which finds either an inconsistent set of constraints (of size bounded by the function of ε) or a truth assignment which satisfies the fraction of at least ρ_∞(Π) — ε of the given constraints. Most of our results hold for both the unweighted and weighted versions of the problem.