Sparsification of binary CSPs

DOI10.1137/19M1242446zbMATH Open1432.68173arXiv1901.00754OpenAlexW2907134641MaRDI QIDQ5220474FDOQ5220474

Authors: Silvia Butti, S. Zivny 

Publication date: 26 March 2020

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

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.

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

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

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

• Twice-Ramanujan sparsifiers
• Spectral sparsification of graphs
• A general framework for graph sparsification
• Graph sparsification by effective resistances
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• The Complexity of General-Valued CSPs
• On multiplicative \(\lambda\)-approximations and some geometric applications
• Graph Sparsification in the Semi-streaming Model
• Title not available (Why is that?)
• Sketching Cuts in Graphs and Hypergraphs
• Bigraphs versus digraphs via matrices
• Spectral Sparsification of Hypergraphs
• On sketching quadratic forms
• Title not available (Why is that?)
• Sparsification of Two-Variable Valued Constraint Satisfaction Problems
• Sparsification of Binary CSPs

Cited In (2)

• Variable Elimination in Binary 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)