  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'\subset
\Pi,w')$ 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)| \neq 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.
