Sparsification of Binary CSPs
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 Benczúr and Karger [Approximating s-t minimum cuts in O͂($n^2$) time, in Proceedings of the Twenty-Eighth …