SPARSIFICATION OF BINARY CSPs.

A cut varepsilon-sparsifier of a weighted graph G is a reweighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of varepsilon. Since their introduction by Benczur and Karger [Approximating s-t minimum cuts in O~ (n2) time, in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC96), 1996, pp. 47-55], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIAM J. Discrete Math., 31 (2017), pp. 1263--1276] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains. [ABSTRACT FROM AUTHOR]