Sparsification of Binary CSPs

Silvia Butti, Stanislav Zivny

A cut $\epsilon$-sparsifier of a weighted graph $G$ is a re-weighted subgraph of $G$ of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of $…