Additive Sparsification of CSPs
Additive Sparsification of CSPs
复制标题
DOI：
10.1145/3625824
复制
发表时间：
2021-06
影响因子：
1.3
通讯作者：
Eden Pelleg;Stanislav Živný
中科院分区：
文献类型：
--
作者：
Eden Pelleg;Stanislav Živný
乘法削减稀疏，介绍了Benczúr和Karger [STOC'96]，已被证明是非常有影响力的，并找到了各种应用。Filtser和Krauthgamer [SIDMA'17]在布尔域上以及Butti和Kauivnnanov [SIDMA'20]在非布尔域上建立了具有其他2变量谓词的图的稀疏性的精确特征。Bansal，Svensson和Trevisan [FOCS'19]引入了一个较弱的稀疏化概念，称为“加法稀疏化”，它不需要图的边缘上的权重。特别是，Bansal等人为图和超图中的切割设计了加法稀疏器的算法。作为我们的主要结果，我们建立了所有的布尔约束满足问题（CSP）允许一个可加稀疏子;也就是说，对于每个布尔谓词P：{0，1}k→ {0，1}的固定元k，我们证明了CSP（P）允许一个可加稀疏子。在我们新引入的非布尔谓词的除一之外的所有稀疏化的概念下，我们证明了CSP（P）对于任意有限域D上的任何谓词P：Dk→ {0，1}都允许一个具有固定元k的可加稀疏化子。
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 : Dk→ { 0,1} of a fixed arity k on an arbitrary finite domain D.