- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture

Martin Weigt and Alexander K. Hartmann*

  • Institute for Theoretical Physics, University of Göttingen, Bunsenstrasse 9, 37073 Göttingen, Germany

  • *Email address: hartmann/weigt@theorie.physik.uni-goettingen.de
PDF

Phys. Rev. E 63, 056127 – Published 26 April, 2001

DOI: https://doi.org/10.1103/PhysRevE.63.056127

Abstract

The minimal vertex-cover (or maximal independent-set) problem is studied on random graphs of finite connectivity. Analytical results are obtained by a mapping to a lattice gas of hard spheres of (chemical) radius 1, and they are found to be in excellent agreement with numerical simulations. We give a detailed description of the replica-symmetric phase, including the size and entropy of the minimal vertex covers, and the structure of the unfrozen component which is found to percolate at a connectivity c≃1.43. The replica-symmetric solution breaks down at c=e≃2.72. We give a simple one-step replica-symmetry-broken solution, and discuss the problems in the interpretation and generalization of this solution.

View figure in article

References (47)

  1. Frontiers in Problem Solving: Phase Transitions and Complexity, edited by T. Hogg, B. A. Huberman, and C. Williams [Art. Intell. 81 (1996)].
  2. O. Dubois, R. Monasson, B. Selman, and R. Zecchina, special issue of Theor. Comput. Sci. (to be published).
  3. M. R. Garey and D. S. Johnson, Computers and Intractability (Freeman, San Francisco, 1979).
  4. D. Mitchell, B. Selman, and H. Levesque, in Proceedings of the 10th National Conference On Artificial Intelligence (AAAI Press/MIT Press, Cambridge, MA, 1992), p. 440.
  5. R. Monasson and R. Zecchina, Phys. Rev. E 56, 1357 (1997).
  6. R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Nature (London) 400, 133 (1999).
  7. G. Biroli, R. Monasson, and M. Weigt, Eur. Phys. J. B 14, 551 (2000).
  8. F. Ricci-Tersenghi, M. Weigt, and R. Zecchina, Phys. Rev. E 63, 026702 (2001).
  9. S. Mertens, Phys. Rev. Lett. 81, 4281 (1998).
  10. M. Mézard and G. Parisi, J. Phys.47, 1285(1986).
  11. J. Houdayer, J. H. Boutet de Monvel, and O. C. Martin, Eur. Phys. J. B 6, 383 (1998).
  12. M. Weigt and A. K. Hartmann, Phys. Rev. Lett. 84, 6118 (2000).
  13. S. Cocco and R. Monasson, Phys. Rev. Lett. 86, 1654 (2001).
  14. M. Weigt and A. K. Hartmann, Phys. Rev. Lett. 86, 1658 (2001).
  15. P. Erdös and A. Rényi, Publ. Math. Inst. Hung. Acad. Sci.5, 17 (1960).
  16. B. Bollobas, Random Graphs (Academic Press, New York, 1985).
  17. J. Harant, Discrete Math. 188, 239 (1998).
  18. C. Caro, Technical Report, Tel Aviv University (1979); V. K. Wei, Bell Lab. Technical Memorandum No. 81-11217-9 (1981)
  19. B. Bollobás and P. Erdös, Math. Proc. Cambridge Philos. Soc. 80, 419 (1976).
  20. P. G. Gazmuri, Network 14, 367 (1984).
  21. A. M. Frieze, Discrete Math. 81, 171 (1990).
  22. R. J. Baxter, Exactly Solved Models in Statistical Mechanics (Academic Press, London, 1982).
  23. F. M. Russo, Phys. Lett. A 239, 17 (1998).
  24. S. Scarpetta, A. de Candia, and A. Coniglio, Phys. Rev. E E55, 4943 (1997).
  25. F. Ricci-Tersenghi, D. A. Stariolo, and J. J. Arenzon, Phys. Rev. Lett. 84, 4473 (2000); Phys. Rev. E 62, 5978 (2000).
  26. M. Nicodemi, A. Coniglio, and H. J. Herrmann, Phys. Rev. E 55, 3962 (1997); J. Phys. A 30, L379 (1997).
  27. M. Nicodemi, J. Phys. I 7, 1365 (1998).
  28. E. Caglioti, V. Loreto, H. J. Herrmann, and M. Nicodemi, Phys. Rev. Lett. 79, 1575 (1997).
  29. M. Nicodemi and A. Coniglio, Phys. Rev. Lett. 82, 916 (1999); J. Phys. C 12, 6601 (2000).
  30. R. Monasson and O. Pouliquen, Physica A 236, 395 (1997).
  31. A. Barrat and V. Loreto, J. Phys. A 33, 4401 (2000).
  32. K. Mehlhorn and St. Näher, The LEDA Platform of Combinatorial and Geometric Computing (Cambridge University Press, Cambridge, 1999); also see http://www.mpi-sb.mpg.de/LEDA/leda.html.
  33. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974).
  34. E. L. Lawler and D. E. Wood, Oper. Res. 14, 699 (1966).
  35. R. E. Tarjan and A. E. Trojanowski, SIAM J. Comput. 6, 537 (1977).
  36. M. Shindo and E. Tomita, Syst. Comput. Jpn.21, 1 (1990).
  37. R. Lüling and B. Monien, Sixth International Parallel Processing Symposium (IEEE Computer Society Press, Los Alamitos, CA, 1992), p. 543.
  38. M. Mézard, G. Parisi, and M. A. Virasoro, Spin Glasses and Beyond (World Scientific, Singapore, 1987).
  39. R. Monasson, J. Phys. A 31, 513 (1998).
  40. M. Bauer and O. Golinelli, Phys. Rev. Lett. 86, 2621 (2001).
  41. C. De Dominicis and P. Mottishaw, J. Phys. A 20, L1267 (1987).
  42. P. Mottishaw and C. De Dominicis, J. Phys. A 20, L375 (1987).
  43. K. Y. M. Wong and D. Sherrington, J. Phys. A 21, L459 (1988).
  44. Y. Y. Goldschmidt and P. Y. Lai, J. Phys. A 23, L775 (1990).
  45. M. Mezard and G. Parisi, e-print cond-mat/0009418.
  46. In principle, a scaling m∼μ−1 can also be plugged in. This would be analogous to infinite-connectivity spin-glass models in the zero-temperature limit, and was also considered in the variational approach [7] to 3 satisfiability. However, its inclusion in the presented formulation leads however to saddle-point equations which could not be solved by the authors.
  47. M. Bauer and O. Golinelli, e-print cond-mat/0102011.

Outline

Information

Phys. Rev. E 63, 056127– Published 26 April, 2001
  • Received 27 November 2000

© 2001 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation