Counting without sampling: new algorithms for enumeration problems using statistical physics

ABSTRACT

We propose a new type of approximate counting algorithms for the problems of enumerating the number of independent sets and proper colorings in low degree graphs with large girth. Our algorithms are not based on a commonly used Markov chain technique, but rather are inspired by recent developments in statistical physics in connection with correlation decay properties of Gibbs measures and its implications to uniqueness of Gibbs measures on infinite trees, reconstruction problems and local weak convergence methods. On a negative side, our algorithms provide ∈-approximations only to the logarithms of the size of a feasible set (also known as free energy in statistical physics). But on the positive side, unlike Markov chain based algorithms, our approach provides deterministic as opposed to probabilistic guarantee on approximations. Moreover, for some regular graphs we obtain explicit values for the counting problem. For example, we show that every 4-regular n-node graph with large girth has asymptotically (1.494 ...)ⁿ independent sets, and in every r-regular graph with n nodes and large girth the number of q ≥ r + 1-proper colorings is asymptotically (q(1-1/q)^r/2)ⁿ for large n. In statistical physics terminology, we compute explicitly the partition function (free energy) in these cases. We extend our results to random regular graphs graphs also. The explicit results obtained in this paper would be hard to derive via Markov chain sampling technique.

REFERENCES

• 1: {AB05} D. Aldous and A. Bandyopadhyay, A survey of max-type recursive distributional equations, Annals of Applied Probability 15 (2005), no. 2, 1047--1110.
• 2: David J. Aldous, The ζ (2) limit in the random assignment problem, Random Structures & Algorithms, v.18 n.4, p.381-418, July 2001 [doi>10.1002/rsa.1015]
• 3: {AS03} D. Aldous and J. M. Steele, The objective method: Probabilistic combinatorial optimization and local weak convergence, Discrete Combinatorial Probability, H. Kesten Ed., Springer-Verlag, 2003.
• 4: {Ban} A. Bandyopadhyay, Hard-core model on random graphs, In preparation.
• 5: {Ban02} A. Bandyopadhyay, Bivariate uniqueness in the logistic fixed point equation, Technical Report 629, Department of Statistics, UC, Berkeley (2002).
• 6: {BSVV} I. Bezakova, D. Stefankovic, V. Vazirani, and E. Vigoda, Improved simulated annealing algorithm for the permanent and combinatorial counting problems, Submitted.
• 7: {BW02} G. Brightwell and P. Winkler, Random colorings of a Cayley tree, in Contemporary Combinatorics, B. Bollobas, ed., Bolyai Society Mathematical Studies, 2002, pp. 247--276.
• 8: Graham R. Brightwell , Peter Winkler, A second threshold for the hard-core model on a Bethe lattice, Random Structures & Algorithms, v.24 n.3, p.303-314, May 2004 [doi>10.1002/rsa.v24:3]
• 9: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 10: Martin Dyer , Alan Frieze , Thomas P. Hayes , Eric Vigoda, Randomly Coloring Constant Degree Graphs, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.582-589, October 17-19, 2004 [doi>10.1109/FOCS.2004.57]
• 11: Martin Dyer , Leslie Ann Goldberg , Mark Jerrum, Counting and sampling H-colourings, Information and Computation, v.189 n.1, p.1-16, 25 February 2004 [doi>10.1016/j.ic.2003.09.001]
• 12: {Dob70} R. L. Dobrushin, Prescribing a system of random variables by the help of conditional distributions, Theory of Probability and its Applications 15 (1970), 469--497.
• 13: {Gam04} D. Gamarnik, Linear phase transition in random linear constraint satisfaction problems, Probability Theory and Related Fields. 129 (2004), no. 3, 410--440.
• 14: {Geo88} H. O. Georgii, Gibbs measures and phase transitions, de Gruyter Studies in Mathematics 9, Walter de Gruyter & Co., Berlin, 1988.
• 15: David Gamarnik , Tomasz Nowicki , Grzegorz Swirszcz, Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method, Random Structures & Algorithms, v.28 n.1, p.76-106, January 2006 [doi>10.1002/rsa.v28:1]
• 16: {GNSb} D. Gamarnik, T. Nowicki, and G. Swirszcz, Dynamics of exponential linear map in functional space, Submitted.
• 17: {JLR00} S. Janson, T. Łuczak, and A. Rucinski, Random graphs, John Wiley and Sons, Inc., 2000.
• 18: {Jon02} J. Jonasson, Uniqueness of uniform random colorings of regular trees, Statistics and Probability Letters 57 (2002), 243--248.
• 19: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 20: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 21: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM (JACM), v.51 n.4, p.671-697, July 2004 [doi>10.1145/1008731.1008738]
• 22: {Kel85} F. Kelly, Stochastic models of computer communication systems, J. R. Statist. Soc. B 47 (1985), no. 3, 379--395.
• 23: Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
• 24: Michael Luby , Eric Vigoda, Approximately counting up to four (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.682-687, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258663]
• 25: László Lovász , Santosh Vempala, Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.650, October 11-14, 2003
• 26: {Mos04} E. Mossel, Survey: information flow on trees, J. Nestril and P. Winkler, editors. Graphs, Morphisms and Statistical Physiscs. DIMACS series in discrete mathematics and theoretical computer science. American Mathematical Society., 2004, pp. 155--170.
• 27: {MP05} M. Mezard and G. Parisi, The cavity method at zero temperature, http://fr.arxiv.org/ps/cond-mat/0207121 (2005).
• 28: {MPV87} M. Mezard, G. Parisi, and M. A. Virasoro, Spin-glass theory and beyond, vol 9 of Lecture Notes in Physics, World Scientific, Singapore, 1987.
• 29: {RBMM04} O. Rivoire, G. Biroli, O. C. Martin, and M. Mezard, Glass models on Bethe lattices, Eur. Phys. J. B 37 (2004), 55--78.
• 30: {Tal01} M. Talagrand, The high temperature case of the K-sat problem, Probability Theory and Related Fields 119 (2001), 187--212.
• 31: {TAl03} M. Talagrand, Parisi formula, Ann. of Mathematics, to apper (2003).
• 32: {Val79} L. G. Valiant, The complexity of computing the permanent, Theoretical computer science 8 (1979), 189--201.
• 33: {War05} J. Warren, Dynamics and endogeny for recursive processes on trees, http://arxiv.org/abs/math.PR/0506038 (2005).
• 34: Dror Weitz, Combinatorial criteria for uniqueness of Gibbs measures, Random Structures & Algorithms, v.27 n.4, p.445-475, December 2005 [doi>10.1002/rsa.v27:4]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory