Butti, SilviaStanislav Zivný2020-03-262020-03-262020Butti S, Zivný S. Sparsification of binary CSPs. SIAM J Discret Math. 2020 Mar 23;34(1):825–42. DOI: 10.1137/19M12424460895-4801http://hdl.handle.net/10230/44049A cut ε-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 ε. Since their intro- duction by Bencz´ur and Karger [STOC’96], cut sparsifiers have proved extremely influen- tial and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIDMA’17] 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.application/pdfeng© Society for Industrial and Applied Mathematicsinfo:eu-repo/semantics/articlehttp://dx.doi.org/10.1137/19M1242446Constraint satisfaction problemsMinimum cutsSparsificationinfo:eu-repo/semantics/openAccess