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 de l'École normale supérieure, 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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2014, 548, pp.10. 〈10.1016/j.tcs.2014.06.040〉
Liste complète des métadonnées
Contributeur : Marc Lelarge <>
Soumis le : mercredi 3 décembre 2014 - 17:31:13
Dernière modification le : vendredi 25 mai 2018 - 12:02:07




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



Consultations de la notice