Sparsification of Binary CSPs

A 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 introduction by Benczúr and Karger [STOC’96], cut sparsifiers have proved extremely influential and found various applicat...

Descrición completa

Detalles Bibliográficos
Main Authors: Butti, S, Zivny, S
Formato: Conference item
Publicado: Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2019