2015/09/06 by Arnold Filtser, Robert Krauthgamer, Filtser, Arnold +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1509.01844
openalex publication_date 2015/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A valued constraint satisfaction problem (VCSP) instance (V,Π,w) is a set of variables V with a set of constraints Π weighted by w. Given a VCSP instance, we are interested in a re-weighted sub-instance (V,Π'⊂ Π,w') such 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|/ε2) constraints if and only if 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 conclude that also systems of 2SAT (or 2LIN) constraints can be sparsified.