Sparsification of Two-Variable Valued CSPs

Arnold Filtser, Robert Krauthgamer

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…