Sparsification of Binary CSPs
A cut ε-sparsifier of a weighted graph G is a re-weighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of ε. Since their introduction by Benczúr and Karger [STOC’96], cut sparsifiers have proved extremely influential and found various applicat...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2019
|
| _version_ | 1797098304083853312 |
|---|---|
| author | Butti, S Zivny, S |
| author_facet | Butti, S Zivny, S |
| author_sort | Butti, S |
| collection | OXFORD |
| description | A cut ε-sparsifier of a weighted graph G is a re-weighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of ε. Since their introduction by Benczúr and Karger [STOC’96], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIDMA’17] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains. |
| first_indexed | 2024-03-07T05:07:34Z |
| format | Conference item |
| id | oxford-uuid:da7375d5-ac8f-4806-a2ca-bd84580ee15e |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:07:34Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:da7375d5-ac8f-4806-a2ca-bd84580ee15e2022-03-27T09:03:21ZSparsification of Binary CSPsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:da7375d5-ac8f-4806-a2ca-bd84580ee15eSymplectic Elements at OxfordSchloss Dagstuhl - Leibniz-Zentrum für Informatik2019Butti, SZivny, SA cut ε-sparsifier of a weighted graph G is a re-weighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of ε. Since their introduction by Benczúr and Karger [STOC’96], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIDMA’17] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains. |
| spellingShingle | Butti, S Zivny, S Sparsification of Binary CSPs |
| title | Sparsification of Binary CSPs |
| title_full | Sparsification of Binary CSPs |
| title_fullStr | Sparsification of Binary CSPs |
| title_full_unstemmed | Sparsification of Binary CSPs |
| title_short | Sparsification of Binary CSPs |
| title_sort | sparsification of binary csps |
| work_keys_str_mv | AT buttis sparsificationofbinarycsps AT zivnys sparsificationofbinarycsps |