Skip to Main content Skip to Navigation
New interface
Journal articles

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

Marc Lelarge 1, 2, 3 Hang Zhou 1 
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique - ENS Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : For a graph G , let Z(G,λ)Z(G,λ) be the partition function of the monomer–dimer system defined by ∑kmk(G)λk∑kmk(G)λk, where mk(G)mk(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 log⁡Z(G,λ)log⁡Z(G,λ) at an arbitrary value λ>0λ>0 within additive error ϵn with high probability. The query complexity of our algorithm does not depend on the size of G and is polynomial in 1/ϵ1/ϵ, and we also provide a lower bound quadratic in 1/ϵ1/ϵ for this problem. This is the first analysis of a sublinear-time approximation algorithm for a #P -complete problem. Our approach is based on the correlation decay of the Gibbs distribution associated with Z(G,λ)Z(G,λ). 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/ϵ1/ϵ and the lower bound is quadratic in 1/ϵ1/ϵ. 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Marc Lelarge Connect in order to contact the contributor
Submitted on : Wednesday, December 3, 2014 - 5:31:13 PM
Last modification on : Thursday, March 17, 2022 - 10:08:44 AM

Links full text



Marc Lelarge, Hang Zhou. Sublinear-time algorithms for monomer–dimer systems on bounded degree graphs. Theoretical Computer Science, 2014, 548, pp.10. ⟨10.1016/j.tcs.2014.06.040⟩. ⟨hal-01090580⟩



Record views