Sparsification of Binary CSPs

DOI10.1137/19M1242446zbMath1432.68173arXiv1901.00754OpenAlexW2907134641MaRDI QIDQ5220474

Silvia Butti, Stanislav Živný

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)

Cites Work

• On Sketching Quadratic Forms
• On Multiplicative $\lambda$-Approximations and Some Geometric Applications
• Sketching Cuts in Graphs and Hypergraphs
• Spectral Sparsification of Graphs
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Graph Sparsification in the Semi-streaming Model
• Bigraphs versus digraphs via matrices
• Twice-Ramanujan Sparsifiers
• Sparsification of Binary CSPs
• Spectral Sparsification of Hypergraphs
• Sparsification of Two-Variable Valued Constraint Satisfaction Problems
• The Complexity of General-Valued CSPs
• A general framework for graph sparsification
• Graph Sparsification by Effective Resistances
• Unnamed Item
• Unnamed Item

This page was built for publication: Sparsification of Binary CSPs