Search

A valued constraint satisfaction problem (VCSP) instance (V, ∏, w) is a set of variables V with a set of constraints n weighted by w. Given a VCSP instance, we are interested in a reweighted subinstance (V, ∏' ⊂ ∏, w') that preserves the value of the given instance (under every assignment to the variables) within factor 1 ± ∈. A well-studied special case is cut sparsification in graphs, which has found various applications. We show that a VCSP instance consisting of a single boolean predicate P(x, y) (e.g., for cut, P = XOR) can be sparsified into O(|V|/∈²) constraints iff the number of inputs that satisfy P is anything but one (i.e., |P-1(1)| ≠ 1). Furthermore, this sparsity bound is tight unless P is a relatively trivial predicate. We con clude that also systems of 2SAT (or 2LIN) constraints can be sparsified. [ABSTRACT FROM AUTHOR]

Abstract: 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, denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints of types from . In the case of sets consisting of finitely many Boolean predicates, we express the limit as the minimum of a certain functional on a convex set of polynomials. Our results yield a robust deterministic algorithm (for a fixed set ) running in time linear in the size of the input and 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. We also compute the values of for several specific predicates P. [Copyright &y& Elsevier]