Journal of Mathematical Physics
Feedback | Help | Exit
   
 
 
 
Previous Article
First passage percolation on locally treelike networks. I. Dense random graphs
We study various properties of least cost paths under independent and identically distributed (iid) disorder for the complete graph and dense Erdős–Rényi random graphs in the conne...

The peculiar phase structure of random graph bisection

J. Math. Phys. 49, 125219 (2008); doi:10.1063/1.3043666

Published 31 December 2008

You are not logged in to this journal. Log in

Allon G. Percus,1 Gabriel Istrate,2 Bruno Gonçalves,3 Robert Z. Sumi,4 and Stefan Boettcher3
1Information Sciences Group, Computer, Computational and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA and Department of Mathematics, UCLA, Los Angeles, California 90095, USA
2eAustria Research Institute, Bd. V. Pârvan 4, cam. 045B, RO-300223 Timisoara, Romania
3Department of Physics, Emory University, Atlanta, Georgia 30322-2430, USA
4Department of Physics, Babes-Bolyai University, RO-400884 Cluj, Romania and eAustria Research Institute, Bd. V. Pârvan 4, cam. 045B, RO-300223 Timisoara, Romania
The mincut graph bisection problem involves partitioning the n vertices of a graph into disjoint subsets, each containing exactly n/2 vertices, while minimizing the number of “cut” edges with an endpoint in each subset. When considered over sparse random graphs, the phase structure of the graph bisection problem displays not only certain familiar properties but also some surprises. It is known that when the mean degree is below the critical value of 2 log 2, the cutsize is zero with high probability. We study how the minimum cutsize increases with mean degree above this critical threshold, finding a new analytical upper bound that improves considerably upon previous bounds. Combined with recent results on expander graphs, our bound suggests the unusual scenario that random graph bisection is replica symmetric up to and beyond the critical threshold, with a replica symmetry breaking transition possibly taking place above the threshold. An intriguing algorithmic consequence is that although the problem is NP-hard, we can conceivably find near-optimal cutsizes (whose ratio to the optimal value approaches 1 asymptotically) in polynomial time for typical instances near the phase transition. ©2008 American Institute of Physics
History: Received 4 August 2008; accepted 17 October 2008; published 31 December 2008
Permalink: http://link.aip.org/link/?JMAPAQ/49/125219/1
BUY THIS ARTICLE   (US$28)
Download PDF (200 kB) View Cart

KEYWORDS and PACS

Keywords
PACS
  • 05.40.-a
    Fluctuation phenomena, random processes, noise, and Brownian motion
  • 02.50.-r
    Probability theory, stochastic processes, and statistics
  • 02.10.Ox
    Combinatorics; graph theory
  • YEAR: 2008

PUBLICATION DATA

ISSN:
0022-2488 (print)   1089-7658 (online)
Publisher:
AIP is a member of CrossRef AIP

REFERENCES (33)
View in Separate Window/Tab
For access to fully linked references, you need to log in. For access to fully linked references, you need to Log in.
  1. Alpert, C. J. and Kahng A. B., “Recent directions in netlist partitioning: a survey,” Dig. Tech. Pap. - Symp. VLSI Technol. 19, 1 (1995).
  2. Benjamini, I., Kozma, G., and Wormald, N., “The mixing time of the giant component of a random graph,” e-print arXiv:math.PR/0610459.
  3. Benjamini, I. and Mossel, E., “On the mixing time of a simple random walk on the supercritical percolation cluster,” Probab. Theory Relat. Fields 125, 408 (2003).
  4. Biroli, G., Monasson, R., and Weigt, M., “A variational description of the ground state structure in random satisfiability problems,” Eur. Phys. J. B 14, 551 (2000).
  5. Boettcher, S., “Extremal Optimization of Graph Partitioning at the Percolation Threshold,” J. Phys. A 32, 5201 (1999).
  6. Boettcher, S. and Percus, A. G., “Nature's way of optimizing,” Artif. Intell. 119, 275 (2000).
  7. Boettcher, S. and Percus, A. G., “Extremal optimization at the phase transition of the 3-coloring problem,” Phys. Rev. E 69, 066703 (2004).
  8. Bollobas, B., Random Graphs (Cambridge University Press, Cambridge, 2001).
  9. Boykov, Y., Veksler, O., and Zabih, R., “Fast approximate energy minimization via graph cuts,” IEEE Trans. Pattern Anal. Mach. Intell. 23, 1222 (2001).
  10. Cheeger, J., “A lower bound for the smallest eigenvalue of the Laplacian,” in Problems in Analysis (Papers Dedicated to Salomon Bochner, 1969), edited by R. C. Gunning (Princeton University Press, Princeton, 1970), pp. 195–199.
  11. Cheeseman, P., Kanefsky, B., and Taylor, W. F., “Where the really hard problems are,” Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI'91) (Morgan Kaufmann, San Mateo, CA, 1991), pp. 331–337.
  12. Erdős, P. and Rényi, A., “On Random Graphs I,” Publ. Math. (Debrecen) 6, 290 (1959).
  13. Fu, Y. and Anderson, P. W., “Application of statistical mechanics to NP-complete problems in combinatorial optimisation,” J. Phys. A 19, 1605 (1986).
  14. Garey, M. R. and Johnson, D. S., Computers and Intractability (Freeman, San Francisco, 1979).
  15. Goel, A., Rai, S., and Krishnamachari, B., “Monotone properties of random geometric graphs have sharp thresholds,” Ann. Appl. Probab. 15, 2535 (2005).
  16. Goldberg, M. K. and Lynch, J. F., “Lower and upper bounds for the bisection width of a random graph,” Congr. Numer. 49, 19 (1985).
  17. Gonçalves, B., Istrate, G., Percus, A. G., and Boettcher, S., “The core peeling algorithm for graph bisection: an experimental evaluation,” Los Alamos National Laboratory Technical Report No. LA-UR 06–6863, 2006.
  18. Holme, P., Kim, B. J., Yoon, C. N., and Han, S. K., “Attack vulnerability of complex networks,” Phys. Rev. E 65, 056109 (2002).
  19. Istrate, G., Kasiviswanathan, S., and Percus, A. G., “The cluster structure of minimum bisections of sparse random graphs,” Los Alamos National Laboratory Technical Report No. LA-UR 06–6566, 2006.
  20. Istrate, G., Kasiviswanathan, S., and Percus, A. G. (unpublished).
  21. Janson, S., Luczak, T., and Ruciński, A., Random Graphs (Wiley, New York, 2000).
  22. Kanter, I. and Sompolinsky, H., “Mean-field theory of spin-glasses with finite coordination number,” Phys. Rev. Lett. 58, 164 (1987).
  23. Kolmogorov, V. and Zabih, R., “What energy functions can be minimized via graph cuts?,” IEEE Trans. Pattern Anal. Mach. Intell. 26, 147 (2004).
  24. Liao, W., “Graph bipartitioning problem,” Phys. Rev. Lett. 59, 1625 (1987).
  25. Liao, W., “Replica-symmetric solution of the graph-bipartitioning problem,” Phys. Rev. A 37, 587 (1988).
  26. [barred L]uczak, M. J. and McDiarmid, C., “Bisecting sparse random graphs,” Random Struct. Algorithms 18, 31 (2001).
  27. Mézard, M. and Parisi, G., “Mean-field theory of randomly frustrated systems with finite connectivity,” Europhys. Lett. 3, 1067 (1987).
  28. Mézard, M., Parisi, G.,and Zecchina, R., “Analytic and algorithmic solutions of random satisfiability problems,” Science 297, 812 (2002).
  29. Mézard, M. and Zecchina, R., “Random K-satisfiability problem: from an analytical solution to an efficient algorithm,” Phys. Rev. E 66, 056126 (2002).
  30. Mitchell, D. G., Selman, B., and Levesque, H. J., “Hard and easy distributions for SAT problems,” Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI Press, Menlo Park, CA, 1992), pp. 459–465.
  31. Penrose, M. D., Random Geometric Graphs (Oxford University Press, Oxford, 2003).
  32. Percus, A. G., Istrate, G., and Moore, C., Computational Complexity and Statistical Physics (Oxford University Press, Oxford, 2006).
  33. Pittel, B., “On tree census and the giant component in sparse random graphs,” Random Struct. Algorithms 1, 311 (1990).

CITING ARTICLES
For access to citing articles, you need to log in.
For access to citing articles, you need to Log in.


Copyright © American Institute of Physics