Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs

DOI10.1016/J.TCS.2014.06.040MaRDI QIDQ401479zbMATH OpenOpenAlexFDO

Authors Marc Lelarge, Hang Zhou

Publication date 27 August 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsgraph algorithmsrandom samplingmatchingscorrelation decay

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Analysis of algorithms (68W40) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For a graph $G$, let $Z(G,lambda)$ be the partition function of the monomer-dimer system defined by $su{m}_k{m}_k(G)lambd{a}^k$, where $m_k(G)$ is the number of matchings of size $k$ in $G$. We consider graphs of bounded degree and develop a sublinear-time algorithm for estimating $logZ(G,lambda)$ at an arbitrary value $lambda>0$ within additive error $epsilonn$ with high probability. The query complexity of our algorithm does not depend on the size of $G$ and is polynomial in $1/epsilon$, and we also provide a lower bound quadratic in $1/epsilon$ for this problem. This is the first analysis of a sublinear-time approximation algorithm for a $$-complete problem. Our approach is based on the correlation decay of the Gibbs distribution associated with $Z(G,lambda)$. We show that our algorithm approximates the probability for a vertex to be covered by a matching, sampled according to this Gibbs distribution, in a near-optimal sublinear time. We extend our results to approximate the average size and the entropy of such a matching within an additive error with high probability, where again the query complexity is polynomial in $1/epsilon$ and the lower bound is quadratic in $1/epsilon$. Our algorithms are simple to implement and of practical use when dealing with massive datasets. Our results extend to other systems where the correlation decay is known to hold as for the independent set problem up to the critical activity.

Recommendations

• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Spatial mixing and the connective constant: optimal bounds
• Spatial mixing and the connective constant: optimal bounds
• Random sampling for the monomer-dimer model on a lattice.
• Approximating the number of monomer-dimer coverings of a lattice.

Cites work

• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 5605086 (Why is no real title available?)
• scientific article; zbMATH DE number 5485444 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• scientific article; zbMATH DE number 5057523 (Why is no real title available?)
• A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• An improved constant-time approximation algorithm for maximum~matchings
• Approximate counting via correlation decay in spin systems
• Approximating average parameters of graphs
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Correlation decay and deterministic FPTAS for counting list-colorings of a graph
• Correlation decay up to uniqueness in spin systems
• Counting independent sets up to the tree threshold
• Counting stars and other small subgraphs in sublinear-time
• Information, Physics, and Computation
• Lee-Yang theorems and the complexity of computing averages
• Lower bounds for sampling algorithms for estimating the average
• Matching theory
• Matchings and walks in graphs
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Random generation of combinatorial structures from a uniform distribution
• Random matchings in regular graphs
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• The complexity of counting in sparse, regular, and planar graphs
• The statistical mechanics of strategic interaction
• Theory of monomer-dimer systems

Cited in

(1)

• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs

This page was built for publication: Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs

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