Additive Sparsification of CSPs

Multiplicative cut sparsifiers, introduced by Benczúr 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 [...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-09
Main Authors: Pelleg, Eden, Živný, Stanislav
Format: Article
Language:English
Subjects:
Algorithms
Boolean
Boolean algebra
Domains
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Multiplicative cut sparsifiers, introduced by Benczúr 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 [SIDMA'17] and non-Boolean domains by Butti and Živný [SIDMA'20]. Bansal, Svensson and Trevisan [FOCS'19] introduced a weaker notion of sparsification termed "additive sparsification", which does not require weights on the edges of the graph. In particular, Bansal et al. designed algorithms for additive sparsifiers for cuts in graphs and hypergraphs. As our main result, we establish that all Boolean Constraint Satisfaction Problems (CSPs) admit an additive sparsifier; that is, for every Boolean predicate \(P:\{0,1\}^k\to\{0,1\}\) of a fixed arity \(k\), we show that CSP(\(P\)) admits an additive sparsifier. Under our newly introduced notion of all-but-one sparsification for non-Boolean predicates, we show that CSP(\(P\)) admits an additive sparsifier for any predicate \(P:D^k\to\{0,1\}\) of a fixed arity \(k\) on an arbitrary finite domain \(D\).
ISSN:2331-8422
DOI:10.48550/arxiv.2106.14757