Sparsification of Binary CSPs
Copyright policy )Sparsification of Binary CSPs
A cut $\varepsilon$-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 $\varepsilon$. 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.
Full version of a STACS'19 paper
- University of Oxford United Kingdom
- Technical University of Berlin Germany
- Technische Universitat Berlin Germany
- Leibniz Association Germany
- TECHNISCHE UNIVERSITAET BERLIN Germany
FOS: Computer and information sciences, 000 Computer science, knowledge, general works, minimum cuts, sparsification, Discrete Mathematics (cs.DM), Constraint satisfaction problems, Sparsification, 004, Minimum cuts, Computer Science, Computer Science - Data Structures and Algorithms, 68Q25, 68W25, Data Structures and Algorithms (cs.DS), constraint satisfaction problems, Computer Science - Discrete Mathematics, ddc: ddc:004
FOS: Computer and information sciences, 000 Computer science, knowledge, general works, minimum cuts, sparsification, Discrete Mathematics (cs.DM), Constraint satisfaction problems, Sparsification, 004, Minimum cuts, Computer Science, Computer Science - Data Structures and Algorithms, 68Q25, 68W25, Data Structures and Algorithms (cs.DS), constraint satisfaction problems, Computer Science - Discrete Mathematics, ddc: ddc:004
citations 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
Citations provided by BIP!Popularity provided by BIP!