Wei Wei, Zhang Renquan, Guo Binghui, Zheng Zhiming
LMIB and School of Mathematics and Systems Sciences, Beihang University, 100191, Beijing, China.
Phys Rev E Stat Nonlin Soft Matter Phys. 2012 Jul;86(1 Pt 2):016112. doi: 10.1103/PhysRevE.86.016112. Epub 2012 Jul 25.
To solve the combinatorial optimization problems, especially the minimal Vertex-cover problem with high efficiency, is a significant task in theoretical computer science and many other subjects. Aiming at detecting the solution space of Vertex-cover, a new structure named mutual-determination is defined and discovered for Vertex-cover on general graphs, which results in the emergence of strong correlations among the unfrozen nodes. Based on the backbones and mutual-determinations with node ranks by leaf removal, we propose a Mutual-determination and Backbone Evolution Algorithm to achieve the reduced solution graph, which provides a graphical expression of the solution space of Vertex-cover. By this algorithm, the whole solution space and detailed structures such as backbones can be obtained strictly when there is no leaf-removal core on the given graph. Compared with the current algorithms, the Mutual-determination and Backbone Evolution Algorithm performs as well as the replica symmetry one in a certain interval but has a small gap higher than the replica symmetric breaking one and has a relatively small error for the exact results. The algorithm with the mutual-determination provides a new viewpoint to solve Vertex-cover and understand the organizations of the solution spaces, and the reduced solution graph gives an alternative way to catch detailed information of the ground/steady states.
高效地解决组合优化问题，尤其是最小顶点覆盖问题，是理论计算机科学和许多其他学科中的一项重要任务。为了检测顶点覆盖的解空间，针对一般图上的顶点覆盖定义并发现了一种名为相互决定的新结构，这导致未冻结节点之间出现强相关性。基于通过叶移除得到的骨干和具有节点秩的相互决定，我们提出了一种相互决定和骨干进化算法来获得简化的解图，该图提供了顶点覆盖解空间的图形表示。通过该算法，当给定图上没有叶移除核时，可以严格获得整个解空间和诸如骨干等详细结构。与当前算法相比，相互决定和骨干进化算法在一定区间内与复制对称算法表现相当，但比复制对称破缺算法略高且与精确结果的误差相对较小。具有相互决定的算法为解决顶点覆盖和理解解空间的组织提供了一个新的视角，简化的解图给出了一种获取基态/稳态详细信息的替代方法。
