Sparsification of binary CSPs

DOI10.1137/19M1242446MaRDI QIDQ5220474zbMATHOpenAlexFDO

Authors Silvia Butti, S. Zivny

Publication date 26 March 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.00754

zbMATH Keywords

constraint satisfaction problemssparsificationminimum cuts

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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'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.

Recommendations

• Sparsification of two-variable valued constraint satisfaction problems
• Best-case and worst-case sparsifiability of Boolean CSPs
• Best-case and worst-case sparsifiability of Boolean CSPs
• A general framework for graph sparsification
• A general framework for graph sparsification

Cites work

• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• A general framework for graph sparsification
• Best-case and worst-case sparsifiability of Boolean CSPs
• Bigraphs versus digraphs via matrices
• Graph Sparsification in the Semi-streaming Model
• Graph sparsification by effective resistances
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• On multiplicative \(\lambda\)-approximations and some geometric applications
• On sketching quadratic forms
• Sketching cuts in graphs and hypergraphs
• Sparsification of Binary CSPs
• Sparsification of two-variable valued constraint satisfaction problems
• Spectral sparsification of graphs
• Spectral sparsification of hypergraphs
• The complexity of general-valued CSPs
• Twice-Ramanujan sparsifiers

Cited in

(5)

• Sparsification of two-variable valued constraint satisfaction problems
• Variable Elimination in Binary CSPs
• Cut sparsifiers for balanced digraphs
• Additive Sparsification of CSPs.
• Sparsification of SAT and CSP Problems via Tractable Extensions

This page was built for publication: Sparsification of binary CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5220474)