Journal article
Sparsification of binary CSPs
- Abstract:
- 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´ur 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Funding
Bibliographic Details
- Publisher:
- Society for Industrial and Applied Mathematics Publisher's website
- Journal:
- SIAM Journal on Discrete Mathematics Journal website
- Volume:
- 34
- Issue:
- 1
- Pages:
- 825-842
- Publication date:
- 2020-03-23
- Acceptance date:
- 2019-12-13
- DOI:
- EISSN:
-
1095-7146
- ISSN:
-
0895-4801
Item Description
- Language:
- English
- Keywords:
- Pubs id:
-
pubs:1077610
- UUID:
-
uuid:6bf4b107-9522-477f-b1cd-7ef0775e235b
- Local pid:
- pubs:1077610
- Source identifiers:
-
1077610
- Deposit date:
- 2019-12-13
Terms of use
- Copyright holder:
- Society for Industrial and Applied Mathematics
- Copyright date:
- 2020
- Rights statement:
- © 2020, Society for Industrial and Applied Mathematics
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record