
arXiv: 2106.14757
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 → { 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 → { 0,1} of a fixed arity k on an arbitrary finite domain D .
graphs, FOS: Computer and information sciences, minimum cuts, sparsification, Discrete Mathematics (cs.DM), Computational aspects of satisfiability, constraint satisfaction, additive sparsification, 004, hypergraphs, Graph theory (including graph drawing) in computer science, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Computer Science - Discrete Mathematics
graphs, FOS: Computer and information sciences, minimum cuts, sparsification, Discrete Mathematics (cs.DM), Computational aspects of satisfiability, constraint satisfaction, additive sparsification, 004, hypergraphs, Graph theory (including graph drawing) in computer science, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
