Sparsification of Binary CSPs
Silvia Butti, Stanislav Živný · SIAM Journal on Discrete Mathematics · 2020
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 Benczúr and Karger [ Approximating s-t minimum cuts in O͂($n^2$) time, in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC'96), 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.