Sparsification of two-variable valued constraint satisfaction problems

DOI10.1137/15M1046186MaRDI QIDQ5270406zbMATH OpenFDO

Authors Arnold Filtser, Robert Krauthgamer

Publication date 23 June 2017

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

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

zbMATH Keywords

MAX-CSPvalued constraint satisfaction problemcut sparsificationBoolean predicates

Mathematics Subject Classification ID

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

Abstract: A valued constraint satisfaction problem (VCSP) instance $(V,Pi,w)$ is a set of variables $V$ with a set of constraints $Pi$ weighted by $w$. Given a VCSP instance, we are interested in a re-weighted sub-instance $(V,P{i}^{\prime }subsetPi,w^{\prime })$ such that preserves the value of the given instance (under every assignment to the variables) within factor $1pmepsilon$. A well-studied special case is cut sparsification in graphs, which has found various applications. We show that a VCSP instance consisting of a single boolean predicate $P(x,y)$ (e.g., for cut, $P=mboxXOR$) can be sparsified into $O(|V|/epsilo{n}^2)$ constraints if and only if the number of inputs that satisfy $P$ is anything but one (i.e., $|P^{-1}(1)|eq1$). Furthermore, this sparsity bound is tight unless $P$ is a relatively trivial predicate. We conclude that also systems of 2SAT (or 2LIN) constraints can be sparsified.

Recommendations

• Best-case and worst-case sparsifiability of Boolean CSPs
• Best-case and worst-case sparsifiability of Boolean CSPs
• Sparsification of binary CSPs
• Skew bisubmodularity and valued CSPs
• Optimal sparsification for some binary CSPs using low-degree polynomials

Cites work

• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• A general framework for graph sparsification
• Bigraphs versus digraphs via matrices
• Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
• 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 -approximations and some geometric applications
• On sketching quadratic forms
• Random sampling in residual graphs
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Sketching cuts in graphs and hypergraphs
• Sparse sums of positive semidefinite matrices
• Spectral sparsification of graphs
• Spectral sparsification via random spanners
• Twice-Ramanujan sparsifiers

Cited in

(8)

• Sparsification of Binary CSPs
• Additive sparsification of CSPs
• Sparsification of binary CSPs
• Best-case and worst-case sparsifiability of Boolean CSPs
• Is constraint satisfaction over two variables always easy?
• The algebraic structure of the densification and the sparsification tasks for CSPs
• Best-case and worst-case sparsifiability of Boolean CSPs
• scientific article; zbMATH DE number 2019637 (Why is no real title available?)

This page was built for publication: Sparsification of two-variable valued constraint satisfaction problems

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