A conjecture on the maximum cut and bisection width in random regular graphs

被引：29

作者：

Zdeborova, Lenka ^{[1
,2
]}

Boettcher, Stefan ^{[3
]}

机构：

[1] Los Alamos Natl Lab, Div Theoret, Los Alamos, NM 87545 USA

[2] Los Alamos Natl Lab, Ctr Nonlinear Studies, Los Alamos, NM 87545 USA

[3] Emory Univ, Dept Phys, Atlanta, GA 30322 USA

来源：

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT | 2010年

基金：

美国国家科学基金会;

关键词：

cavity and replica method; spin glasses (theory); random graphs; networks; MEAN-FIELD THEORY; SPIN-GLASSES; EXTREMAL OPTIMIZATION; BETHE LATTICE; BOUNDS; MODEL;

D O I：

10.1088/1742-5468/2010/02/P02020

中图分类号：

O3 [力学];

学科分类号：

08 ; 0801 ;

摘要：

The asymptotic properties of random regular graphs are objects of extensive study in mathematics and physics. In this paper we argue, using the theory of spin glasses in physics, that in random regular graphs the maximum cut size asymptotically equals the number of edges in the graph minus the minimum bisection size. Maximum cut and minimal bisection are two famous NP-complete problems with no known general relation between them; hence our conjecture is a surprising property for random regular graphs. We further support the conjecture with numerical simulations. A rigorous proof of this relation is an obvious challenge.

引用

页数：13

共 38 条

[1] RECENT DIRECTIONS IN NETLIST PARTITIONING - A SURVEY [J].

ALPERT, CJ ;

KAHNG, AB .

INTEGRATION-THE VLSI JOURNAL, 1995, 19 (1-2) :1-81

[2]

BERTONI A, 2006, LECT NOTES COMPUTER, P78

[3] Nature's way of optimizing [J].

Boettcher, S ;

Percus, A .

ARTIFICIAL INTELLIGENCE, 2000, 119 (1-2) :275-286

[4] Numerical results for ground states of mean-field spin glasses at low connectivities [J].

Boettcher, S .

PHYSICAL REVIEW B, 2003, 67 (06)

[5] Extremal optimization of graph partitioning at the percolation threshold [J].

Boettcher, S .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1999, 32 (28) :5201-5211

[6] Numerical results for ground states of spin glasses on Bethe lattices [J].

Boettcher, S .

EUROPEAN PHYSICAL JOURNAL B, 2003, 31 (01) :29-39

[7] Jamming model for the extremal optimization heuristic [J].

Boettcher, S ;

Grigni, M .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 2002, 35 (05) :1109-1123

[8] Extremal optimization for graph partitioning [J].

Boettcher, S ;

Percus, AG .

PHYSICAL REVIEW E, 2001, 64 (02) :13

[9] Optimization with extremal dynamics [J].

Boettcher, S ;

Percus, AG .

PHYSICAL REVIEW LETTERS, 2001, 86 (23) :5211-5214

[10] THE ISOPERIMETRIC NUMBER OF RANDOM REGULAR GRAPHS [J].

BOLLOBAS, B .

EUROPEAN JOURNAL OF COMBINATORICS, 1988, 9 (03) :241-244

← 1 2 3 4 →