Sparsification of Binary CSPs

DOI10.4230/LIPICS.STACS.2019.17MaRDI QIDQ5090464zbMATH OpenOpenAlexFDO

Authors Silvia Butti, S. Zivny

Publication date 18 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/10256/pdf/LIPIcs-STACS-2019-17.pdf/

zbMATH Keywords

constraint satisfaction problemssparsificationminimum cuts

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Sparsification of binary CSPs
• Additive Sparsification of CSPs.
• Sparsification of two-variable valued constraint satisfaction problems
• Best-case and worst-case sparsifiability of Boolean CSPs

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 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

(6)

• Additive Sparsification of CSPs.
• Variable Elimination in Binary CSPs
• Sparsification of SAT and CSP Problems via Tractable Extensions
• Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism
• Sparsification of binary CSPs
• The algebraic structure of the densification and the sparsification tasks for CSPs

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 Q5090464)