Additive sparsification of CSPs

Multiplicative cut sparsifiers, introduced by Bencz´ur and Karger [STOC’96], have proved extremely influential and found various applications. Precise characterisations were established for sparsifiability of graphs with other 2-variable predicates on Boolean domains by Filtser and Krauthgamer [SIDM...

Descrición completa

Detalles Bibliográficos
Main Authors: Pelleg, E, Zivny, S
Formato: Journal article
Idioma:English
Publicado: Association for Computing Machinery 2023