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...
| Main Authors: | , |
|---|---|
| 格式: | Journal article |
| 语言: | English |
| 出版: |
Association for Computing Machinery
2023
|
| _version_ | 1826311481298255872 |
|---|---|
| author | Pelleg, E Zivny, S |
| author_facet | Pelleg, E Zivny, S |
| author_sort | Pelleg, E |
| collection | OXFORD |
| description | 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 [SIDMA’17] and non-Boolean domains by Butti and Zivn´y [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. |
| first_indexed | 2024-03-07T08:10:27Z |
| format | Journal article |
| id | oxford-uuid:fcfd092a-ab33-4bd1-936f-9ca22b37d27c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:10:27Z |
| publishDate | 2023 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:fcfd092a-ab33-4bd1-936f-9ca22b37d27c2023-11-20T09:45:14ZAdditive sparsification of CSPsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:fcfd092a-ab33-4bd1-936f-9ca22b37d27cEnglishSymplectic ElementsAssociation for Computing Machinery2023Pelleg, EZivny, SMultiplicative 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 [SIDMA’17] and non-Boolean domains by Butti and Zivn´y [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. |
| spellingShingle | Pelleg, E Zivny, S Additive sparsification of CSPs |
| title | Additive sparsification of CSPs |
| title_full | Additive sparsification of CSPs |
| title_fullStr | Additive sparsification of CSPs |
| title_full_unstemmed | Additive sparsification of CSPs |
| title_short | Additive sparsification of CSPs |
| title_sort | additive sparsification of csps |
| work_keys_str_mv | AT pellege additivesparsificationofcsps AT zivnys additivesparsificationofcsps |