Statistical physics of hard combinatorial optimization：Vertex cover problem

doi:10.1088/1674-1056/23/7/078901

Abstract Typical-case computation complexity is a research topic at the boundary of computer science, applied mathematics, and statistical physics. In the last twenty years, the replica-symmetry-breaking mean field theory of spin glasses and the associated message-passing algorithms have greatly deepened our understanding of typical-case computation complexity. In this paper, we use the vertex cover problem, a basic nondeterministic-polynomial (NP)-complete combinatorial optimization problem of wide application, as an example to introduce the statistical physical methods and algorithms. We do not go into the technical details but emphasize mainly the intuitive physical meanings of the message-passing equations. A nonfamiliar reader shall be able to understand to a large extent the physics behind the mean field approaches and to adjust the mean field methods in solving other optimization problems.

Keywords: spin glass energy minimization replica symmetry breaking belief propagation

Received: 20 March 2014
Revised: 22 May 2014
Accepted manuscript online:

PACS:	89.20.Ff	(Computer science and technology)
	75.10.Nr	(Spin-glass and other random models)
	02.10.Ox	(Combinatorics; graph theory)
	05.10.&ndash
	a

Fund: Project supported by the National Basic Research Program of China (Grant No. 2013CB932804), the Knowledge Innovation Program of Chinese Academy of Sciences (Grant No. KJCX2-EW-J02), and the National Natural Science Foundation of China (Grant Nos. 11121403 and 11225526).

Corresponding Authors: Zhou Hai-Jun
E-mail: zhouhj@itp.ac.cn

About author: 89.20.Ff; 75.10.Nr; 02.10.Ox; 05.10.–a

Cite this article:

Zhao Jin-Hua (赵金华), Zhou Hai-Jun (周海军) Statistical physics of hard combinatorial optimization：Vertex cover problem 2014 Chin. Phys. B 23 078901

[1]	Cook S A 1971 Proceedings of the 3rd Annual ACM Symposium on Theory of Computing edited by Lewis P M, Fischer M J, Hopcroft J E, Rosenberg A L, Thatcher J W and Young P R (New York) p. 151
[2]	Karp R M 1972 Complexity of Computer Computations (New York: Plenum Press) p. 85
[3]	Garey Mand Johnson D S 1979 Computers and Intractability: A Guide to the Theory of NP-Completeness (San Francisco: Freeman)
[4]	Papadimitriou C and Steiglitz K 1998 Combinatorial Optimization: Algorithms and Complexity (New York: Dover)
[5]	Cheeseman P, Kanefsky B and Taylor W 1991 Proceedings 12th Int. Joint Conf. on Artificial Intelligence (Sydney) p. 163
[6]	Mézard M, Parisi G and Virasoro M A 1987 Spin Glass Theory and Beyond (Singapore: World Scientific)
[7]	Nishimori H 2001 Statistical Physics of Spin Glasses and Information Processing (Oxford: Oxford University Press)
[8]	Mézard M and Montanari A 2009 Information, Physics, and Computation (New York: Oxford Unversity Press)
[9]	Talagrand M 2003 Spin Glasses (Berlin: Springer)
[10]	Hartmann A K and Weigt M 2005 Phase Transitions in Combinatorial Optimization Problems (Weinhei: Wiley-VCH)
[11]	Mézard M and Parisi G 2001 Eur. Phys. J. B 20 217
[12]	Mézard M and Parisi G 2003 J. Stat. Phys. 111 1
[13]	Mézard M and Parisi G 1986 J. Physique 47 1285
[14]	Monasson R and Zecchina R 1997 Phys. Rev. E 56 1357
[15]	Mézard M, Parisi G and Zecchina R 2002 Science 297 812
[16]	Mézard M and Zecchina R 2002 Phys. Rev. E 66 056126
[17]	Montanari A, Ricci-Tersenghi F and Semerjian G 2008 J. Stat. Mech.: Theor. Exp. P04004
[18]	Krzakala F, Montanari A, Ricci-Tersenghi F, Semerjian G and Zdeborová L 2007 Proc. Natl. Acad. Sci. USA 104 10318
[19]	Franz S, Leone M, Ricci-Tersenghi F and Zecchina R 2001 Phys. Rev. Lett. 87 127209
[20]	Cocco S, Dubois O, Mandler J and Monasson R 2003 Phys. Rev. Lett. 90 047205
[21]	Mézard M, Ricci-Tersenghi F and Zecchina R 2003 J. Stat. Phys. 111 505
[22]	Weigt M and Hartmann A K 2000 Phys. Rev. Lett. 84 6118
[23]	Weigt M and Hartmann A K 2001 Phys. Rev. Lett. 86 1658
[24]	Weigt M and Hartmann A K 2001 Phys. Rev. E 63 056127
[25]	Hartmann A K and Weigt M 2003 J. Phys. A: Math. Gen. 36 11069
[26]	Zhou H J 2003 Eur. Phys. J. B 32 265
[27]	Weigt M and Zhou H J 2006 Phys. Rev. E 74 046110
[28]	Zhou J and Zhou H J 2009 Phys. Rev. E 79 020103
[29]	Zhang P, Zeng Y and Zhou H J 2009 Phys. Rev. E 80 021122
[30]	Dall’Asta L, Pin P and Ramezanpour A 2009 Phys. Rev. E 80 061136
[31]	Mézard M and Tarzia M 2007 Phys. Rev. E 76 041124
[32]	Mézard M, Tarzia M and Toninelli C 2008 J. Phys. C: Conf. Ser. 95 012019
[33]	van Mourik J and Saad D 2002 Phys. Rev. E 66 056120
[34]	Mulet R, Pagnani A, Weigt M and Zecchina R 2002 Phys. Rev. Lett. 89 268701
[35]	Zdeborová L and Krzakala F 2007 Phys. Rev. E 76 031131
[36]	Karp R M and Sipser M 1981 Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (NJ: Wiley-IEEE Computer Society Press) p. 364
[37]	Zhou H J and Ou-Yang Z C 2003 arXiv:0309348v1 [cond-mat]
[38]	Zdeborová L and Mézard M 2006 J. Stat. Mech.: Theor. Exp. P05003
[39]	Zhou H J 2013 Eur. Phys. J. B 86 455
[40]	Breitbart Y, Chan C, Garofalakis M, Rastogi R and Silberschatz A 2001 Proceedings of IEEE INFOCOM' 2001 (Anchorage) p. 933
[41]	Park K and Lee H 2001 Proceedings ACM SIGCOM 2001 (San Diego)
[42]	Gomez-Gardenes J, Echenique P and Moreno Y 2006 Eur. Phys. J. B 49 259
[43]	Huang H, Raymond J and Wong K Y M 2014 J. Stat. Phys. (in press) (2012 arXiv:1209.4134 [cond-mat.dis-nn])
[44]	Harant J 1998 Discr. Math. 188 239
[45]	Caro C 1979 Technical Reports (Tel-Aviv University)
[46]	Wei V K 1981 Techinical Reports 81-11217-9 (Bell Laboratories NJ)
[47]	Harant J 2011 Disc. Appl. Math. 159 966
[48]	Harant J 2006 Discussiones Mathematicae Graph Theory 26 431
[49]	Angel E, Campigotto R and Laforest C 2013 Disc. Appl. Math. 161 847
[50]	Bollobás B 2001 Random Graphs (2nd edn.) (Cambridge: Cambridge University Press)
[51]	Erdös P and Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[52]	Gazmuri P G 1984 Network 14 367
[53]	Dani V and Moore C 2011 Lect. Notes Comput. Sci. 6845 472
[54]	Frieze A M 1990 Discr. Math. 81 171
[55]	Bauer M and Golinelli O 2001 Eur. Phys. J. B 24 339
[56]	Newman M E J and Barkema G T 1999 Monte Carlo Methods in Statistical Physics (USA: Oxford University Press)
[57]	Landau D and Binder K 2013 A Guide to Monte Carlo Simulations in Statistical Physics (3rd edn.) (Cambridge: Cambrige University Press)
[58]	Bathel W and Hartmann A K 2004 Phys. Rev. E 70 066120
[59]	Marinari K and Paris G 1992 Europhys. Lett. 19 45
[60]	Hukushima K and Nemoto K 1996 J. Phys. Soc. Jpn. 65 1604
[61]	Zhou H J 2005 Phys. Rev. Lett. 94 217203
[62]	Zhou H J 2012 Phys. Rev. Lett. 109 199901
[63]	Liu Y Y, Csóka E, Zhou H J and Pósfai M 2012 Phys. Rev. Lett. 109 205703
[64]	Zhou H J 2014 Spin Glasses and Message Passing (in preparation)
[65]	Wei W, Zhang R, Guo B and Zhang Z 2012 Phys. Rev. E 86 016112
[66]	Binder K and Young A P 1986 Rev. Mod. Phys. 58 801
[67]	Bethe H A 1935 Proc. R. Soc. London A 150 552
[68]	Peierls R 1936 Proc. R. Soc. London A 154 207
[69]	Peierls R 1936 Proc. Camb. Phil. Soc. 32 477
[70]	Xiao J Q and Zhou H J 2011 J. Phys. A: Math. Theor. 44 425001
[71]	Zhou H J and Wang C 2012 J. Stat. Phys. 148 513
[72]	Bramoullé Y and Kranton R 2007 J. Econ. Theory 135 478
[73]	Galeotti A, Goyal S, Jackson M, Vega-Redondo F and Yariv L 2010 Rev. Econ. Stud. 77 218
[74]	Ritort F and Sollich P 2003 Add. Phys. 52 219
[75]	Brešar B, Kardoš F, Katrenič J and Semanišin G 2011 Disc. Appl. Math. 159 1189
[76]	Novotný M 2010 Lect. Notes Comput. Sci. 6033 106

[1]	Low-loss belief propagation decoder with Tanner graph in quantum error-correction codes Dan-Dan Yan(颜丹丹), Xing-Kui Fan(范兴奎), Zhen-Yu Chen(陈祯羽), and Hong-Yang Ma(马鸿洋). Chin. Phys. B, 2022, 31(1): 010304.
[2]	Excess-iron driven spin glass phase in Fe_1+yTe_1-xSe_x Long Tian(田龙), Panpan Liu(刘盼盼), Tao Hong(洪涛), Tilo Seydel, Xingye Lu(鲁兴业), Huiqian Luo(罗会仟), Shiliang Li(李世亮), and Pengcheng Dai(戴鹏程). Chin. Phys. B, 2021, 30(8): 087402.
[3]	Doping effect on the structure and physical properties of quasi-one-dimensional compounds Ba₉Co₃(Se_1-xS_x)₁₅ (x = 0-0.2) Lei Duan(段磊), Xian-Cheng Wang(望贤成), Jun Zhang(张俊), Jian-Fa Zhao(赵建发), Wen-Min Li(李文敏), Li-Peng Cao(曹立朋), Zhi-Wei Zhao(赵志伟), Changjiang Xiao(肖长江), Ying Ren(任瑛), Shun Wang(王顺), Jinlong Zhu(朱金龙), and Chang-Qing Jin(靳常青). Chin. Phys. B, 2021, 30(10): 106101.
[4]	Synthesis, structure, and properties of Ba₉Co₃Se₁₅ with one-dimensional spin chains Lei Duan(段磊), Xian-Cheng Wang(望贤成), Jun Zhang(张俊), Jian-Fa Zhao(赵建发), Li-Peng Cao(曹立朋), Wen-Min Li(李文敏), Run-Ze Yu(于润泽), Zheng Deng(邓正), Chang-Qing Jin(靳常青). Chin. Phys. B, 2020, 29(3): 036102.
[5]	Spin glassy behavior and large exchange bias effect in cubic perovskite Ba_0.8Sr_0.2FeO_3-δ Yu-Xuan Liu(刘宇轩), Zhe-Hong Liu(刘哲宏), Xu-Bin Ye(叶旭斌), Xu-Dong Shen(申旭东), Xiao Wang(王潇), Bo-Wen Zhou(周博文), Guang-Hui Zhou(周光辉), You-Wen Long(龙有文). Chin. Phys. B, 2019, 28(6): 068104.
[6]	Recent progress on magnetic-field studies on quantum-spin-liquid candidates Zhen Ma(马祯), Kejing Ran(冉柯静), Jinghui Wang(王靖珲), Song Bao(鲍嵩), Zhengwei Cai(蔡正蔚), Shichao Li(李世超), Jinsheng Wen(温锦生). Chin. Phys. B, 2018, 27(10): 106101.
[7]	Link prediction in complex networks via modularity-based belief propagation Darong Lai(赖大荣), Xin Shu(舒欣), Christine Nardini. Chin. Phys. B, 2017, 26(3): 038902.
[8]	Magnetic phase diagrams of Fe-Mn-Al alloy on the Bethe lattice Erhan Albayrak. Chin. Phys. B, 2017, 26(2): 020502.
[9]	Double spin-glass-like behavior and antiferromagnetic superexchange interaction between Fe³⁺ ions in α-Ga_2-xFe_xO₃ (0 ≤ x ≤ 0.4) Lv Yi-Fei (吕益飞), Xiang Jian-Yong (向建勇), Wen Fu-Sheng (温福昇), Lv Wei-Ming (吕伟明), Hu Wen-Tao (胡文涛), Liu Zhong-Yuan (柳忠元). Chin. Phys. B, 2015, 24(3): 037502.
[10]	Spin frustration and magnetic ordering in triangular lattice antiferromagnet Ca₃CoNb₂O₉ Dai Jia (代佳), Zhou Ping (周萍), Wang Peng-Shuai (王朋帅), Pang Fei (庞斐), Tim J. Munsie, Graeme M. Luke, Zhang Jin-Shan (张金珊), Yu Wei-Qiang (于伟强). Chin. Phys. B, 2015, 24(12): 127508.
[11]	Observation of spin glass transition in spinel LiCoMnO₄ Chen Hong (陈红), Yang Xu (杨旭), Zhang Pei-Song (张培松), Liang Lei (梁磊), Hong Yuan-Ze (洪源泽), Wei Ying-Jin (魏英进), Chen Gang (陈岗), Du Fei (杜菲), Wang Chun-Zhong (王春忠). Chin. Phys. B, 2015, 24(12): 127501.
[12]	Asymmetric exchange bias training effect in spin glass (FeAu)/FeNi bilayers Rui Wen-Bin (芮文彬), He Mao-Cheng (何茂诚), You Biao (游彪), Shi Zhong (时钟), Zhou Shi-Ming (周仕明), Xiao Ming-Wen (肖明文), Gao Yuan (高远), Zhang Wei (张维), Sun Li (孙力), Du Jun (杜军). Chin. Phys. B, 2014, 23(10): 107502.
[13]	Spin-correlation function of the fully frustrated Ising model and ± J Ising spin glass on the square lattice M Y Ali, J Poulter. Chin. Phys. B, 2013, 22(6): 067502.
[14]	The synthesis and exchange bias effect of monodisperse NiO nanocrystals Duan Han-Ning(段寒凝), Yuan Song-Liu(袁松柳), Zheng Xian-Feng(郑先锋), and Tian Zhao-Ming(田召明) . Chin. Phys. B, 2012, 21(7): 078101.
[15]	Spin glass dynamics in RKKY interacting disordered magnetic system Zhang Kai-Cheng(张开成) and Song Peng-Yun(宋朋云). Chin. Phys. B, 2010, 19(9): 097105.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Statistical physics of hard combinatorial optimization：Vertex cover problem

Cite this article:

Online attention