title: Detecting the solution space of vertex cover by mutual determinations and backbones.
abstract: 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.
authors.affiliation: LMIB and School of Mathematics and Systems Sciences, Beihang University, 100191, Beijing, China.
authors.forename: Wei
authors.initials: W
authors.lastname: Wei
authors.forename: Renquan
authors.initials: R
authors.lastname: Zhang
authors.forename: Binghui
authors.initials: B
authors.lastname: Guo
authors.forename: Zhiming
authors.initials: Z
authors.lastname: Zheng
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008962:Models, Theoretical; D009716:Numerical Analysis, Computer-Assisted