Sparsification of Two-Variable Valued CSPs

Abstract

A valued constraint satisfaction problem (VCSP) instance $(V,\Pi ,w)$ is a set of variables $V$ with a set of constraints $\Pi$ weighted by $w$. Given a VCSP instance, we are interested in a re-weighted sub-instance $(V,{\Pi }^{\prime }\subset \Pi ,w^{\prime })$ such that preserves the value of the given instance (under every assignment to the variables) within factor $1\pm \epsilon$. 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=\mbox{XOR}$) can be sparsified into $O(|V|/{\epsilon }^2)$ constraints if and only if the number of inputs that satisfy $P$ is anything but one (i.e., $|P^{-1}(1)|\ne 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.

References in corpus (7)

• Sketching Cuts in Graphs and Hypergraphs
• On Sketching Quadratic Forms
• Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
• Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
• The Sketching Complexity of Graph Cuts
• A Sketching Algorithm for Spectral Graph Sparsification
• Graph Sparsification in the Semi-streaming Model