Determining the Solution Space of Vertex-Cover by Interactions and Backbones

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 interaction between nodes is defined and discovered for random graph, which results in the emergence of the frustration and long-range correlation phenomenon. Based on the backbones and interactions with a node adding process, we propose an Interaction and Backbone Evolution Algorithm to achieve the reduced solution graph, which has a direct correspondence to the solution space of Vertex-cover. By this algorithm, the whole solution space can be obtained strictly when there is no leaf-removal core on the graph and the odd cycles of unfrozen nodes bring great obstacles to its efficiency. Besides, this algorithm possesses favorable exactness and has good performance on random instances even with high average degrees. The interaction with the algorithm provides a new viewpoint to solve Vertex-cover, which will have a wide range of applications to different types of graphs, better usage of which can lower the computational complexity for solving Vertex-cover.


INTRODUCTION
The minimal vertex-cover problem (Vertex-cover) belongs to one of Karp's 21 NPcomplete problems [1] and the six basic NP-complete problems [2,3], which is considered as one of the classical problems in theoretical computer science. The aim of this problem is to mark a minimum subset of vertices such that there are at least one vertex of each edge in the subset. There are a large number of applications of this problem in the related real networks, such as immunization strategies in networks [4] and monitoring of internet traffic [5].
There is a threshold behavior of the minimum vertex-cover problem on the Erdös-Rényi random graph [6]. It means that the typical running time of algorithms changes to exponential from polynomial when the order parameter becomes lager than the Euler number e [7,8]. This phase transition phenomenon is considered to have intrinsic correspondence with the clustering structure of solution space which have already been observed in statistical physics when studying spin glasses [9,10]. Although most statistical physicists believe that the clustering structure leads to the failure of replica symmetry, the details of the relation between searching solutions and the structure are not well established, and how the clustering structure looks like is far from being clear for most models [11][12][13]. From an algorithmic point of view, the solutions' structure makes great effects on the algorithm to find the solutions, which sets barriers to local searching algorithms and makes the computation expensive [14,15]. So the features of solutions' structure are explored by different approaches. Till now, some typical structures such as clustering, backbone, backdoor [16] and frustration [17], have been widely investigated to understand the structure of solutions more clearly. Especially, H. Zhou [17,18] has proposed the long-range frustration structure and F. Krzakala [19] has provided a formal definition as long-range correlation. The longrange correlation and bakbone structures are treated as the origin of the replica symmetric breaking and the high computational complexity. And, based on the analysis of these typical characteristics of the solution space, many efficient searching algorithms are proposed to solve NP-complete problems, such as Belief Propagation and Survey Propagation [20][21][22].
In this paper, a mutual-determination structure is proposed by statistical mechanic approach to investigate the solution space of the minimum vertex-cover problem. This structure reflects the feature of the Hamming distance [23,24] among solutions and describes how tight the correlations among unfrozen variables are. By this structure, we can detect the equivalent variables in the solution space [25], i.e., the variables must take the same or the opposite Boolean values. Furthermore, based on the existence of the mutual-determination in the solution space of Vertex-cover, the ranks of nodes of a graph by the leaf-removal process are provided to describe the influence orders of leaves in different levels. Taking the advantage of the leaf-removal ranks and the relationship of mutual-determination with the backbone and unfrozen variables, we can have a much clear understanding of the evolution of the states in the solution space when a new node is added, and a reduced solution graph is defined to exactly express the structural information of the solution (sub-)space. Finally, an algorithm named Mutual-determination and Backbone Evolution Algorithm is proposed by the evolution of the mutual-determinations and backbones on the reduced solution graph, and some analysis and numerical experiments are given to verify its efficiency and adaptability. This algorithm is complete to find the whole solution space of Vertex-cover when there is no leaf-removal core in the graph, otherwise an approximated one with relatively better efficiency than the replica symmetry methods.

DEFINITION OF INTERACTION
A vertex cover on an undirected graph G(N, M) with N nodes and M edges is a subset S = {i 1 , i 2 , · · · , i m } of its nodes such that every edge has at least one endpoint in S. The minimum vertex-cover problem is an optimization problem to find the minimum size of a vertex cover on a given graph. Mapped to spin-glass model, energy function of the minimum vertex-cover problem can be written as where E(G) denotes the edge set and (i, j)s are edges in it, spin/variable σ i = −1 if node i ∈ S (covered) and σ i = 1 otherwise. Then, different energy levels are produced by different assignments or configurations in terminology of spin-glass theory. The assignments with the lowest energy are named solutions/ground states, and the set of all these solutions achieving the lowest energy (minimum vertex cover) is named solution space S.
Backbones [16] and long-range correlations [17,19] are both the typical structures of solution space of combinatorial optimization problems, which have been well studied in 3 algorithmic and statistical analysis. In the solution space S, spin σ i is frozen or called backbone if it takes the same value in all solutions; otherwise it is unfrozen. For an unfrozen spin σ i , if it taking some value will make influence on infinite number of other spins (assumed O(N) with the total number of N spins), it belongs to long-range correlation [18,19].
Recent research suggests that the complicated organizations of the solutions of combinatorial optimizations, e.g., backbones and long-range correlations, would be the kernel reason for the algorithmic hardness to find a solution for large-scale combinatorial optimization problems with massive constraints and variables [26]. To study the solution space S of Vertex-cover, we classify the variables as unfrozen, positively frozen (frozen to +1) and negatively frozen (frozen to −1) variables.
As a generalization of the backbone and long-range correlation, a new structure named mutual-determination is proposed to achieve a better understanding of the solution space, which can be viewed as an interactive relation of unfrozen variables in the solution space. If two unfrozen variables form a mutual-determination, the fixation of the assignment of any one will result in the fixation of the other in the solution space. Indeed, it is a special relation implied by the constraints that two unfrozen variables can be mutually determined by each other, i.e., if two unfrozen variables σ i , σ j form a mutual-determination, then σ i + σ j = 0.
When two unfrozen nodes form mutual-determination for Vertex-cover, it means that if one of them is covered, the other should be uncovered, and there is one and only one should be covered for this pair of nodes.
By the famous survey propagation algorithm [21], it takes advantage of the idea of the backbone and long-range correlation to gradually eliminate variables and constraints of the original problem in size, and achieves excellent performance for solving 3-SAT, Vertexcover, etc. As the motivation for proposing the mutual-determination structure and for that the variables in interactive relations are equivalent variables, we can use a simple logic σ j = −σ i to decrease the number of variables in the original problem to obtain new algorithmic strategies. In the following sections, we will use the backbones and mutualdeterminations to analyze the solution space of Vertex-cover. There are three leaves in the graph which are marked by the red rectangles in subgraph (2)(3)(4), and the relations among the nodes are revealed by the constraints in the leaves for Vertex-cover.

REDUCED SOLUTION GRAPH OF VERTEX-COVER
To study the solution space of Vertex-cover, the leaf removal [29] should be mentioned as inspiration. Given a graph G, a leaf is a couple of nodes {v, w} in which the first one has degree 1 and the second one is the only neighbor of it. Here, node v is a pendant point in the graph, node w acts as a petiole, and for the same petiole there may be more than one pendant points connecting it. To define the leaf removal, if the nodes pair {v, w} is a leaf in graph G, remove the two nodes with the edges touching them. It is very interesting that the leaf removal process can destroy all the leaves in graph G and can produce new leaves for the rest graph. In Figure 1, a leaf removal process for a simple graph is shown.
By this leaf removal process, we can find that there exist some graphs which have no leaf removal core until the termination of this process, which means that each node belongs to a leaf in the graph. For the Vertex-cover of these graphs, to obtain the minimum vertex cover for the graph, there is one and only one node should be covered for each leaf. By the results in [29], a trivial minimum vertex cover can be obtained by making all the petioles covered with all the pendant points uncovered in different levels of leaves, e.g., making the nodes {c, e, g} or {c, e, f } covered and the rest uncovered leads to minimum vertex covers. Here, we will take use of this trivial solution to construct a relationship between/among nodes in a leaf.
In Figure 1 core for the given graph, and whether this expression is also effective for general graphs with leaf-removal cores and how to obtain the reduced solution graph of Vertex-cover will be discussed in the following.
In order to have a convenient analysis of the reduced solution graph, the leaf-removal [29] sequence is very important. Here, we take advantage of the sequence of the leaf removal to define the rank of each node: Step 1: All the pendant points in the graph are assigned to sequence order/rank 1, and their neighbors (the petioles) have rank 2; Step 2: Remove the leaves with edges connecting them from the graph. After the leaf removal, all the new produced pendant points are assigned to rank 3, and their corresponding petioles have rank 4; Step 3: Repeat the steps 1-2 and assign increasing ranks until their are no new leaves produced. If there is still a leaf-removal core after the above two steps, assign the nodes in the core with ranks according to their already ranked neighbors by gradually increase.

VERTEX-COVER
In this section, we concern on achieving the reduced solution graph S(G) by determining the states of the nodes one by one following the leaf removal sequence/ranks. This process is fulfilled by a method similar to the cavity method, and for each node its state is determined by the local environment of itself. Considering a new node i connected to a graph G with k edges, the newly produced graph is denoted by G ′ . For the neighborhood of node i, there are three kinds of neighbors: positively frozen ones, negatively frozen ones and unfrozen ones.

Local evolution of mutual-determinations and backbones
In this subsection, we consider the different local environments of a new node i, and investigate the state determination and evolution of it and associated nodes. Taking advantage of the analysis in [18], we first study the following four cases: • Case A: only one of its neighbors is positively frozen in G; some other neighbors are unfrozen nodes which can take spin value −1 simultaneously.
In case A, energy increase is unavoidable when node i is added. When σ i takes value −1 (covered), its neighbors of nodes are free to take their spin values in the original G, and new covers of the new graph G ′ come out with the lowest energy; when σ i takes value 1, the positively frozen neighbor should be changed to an unfrozen node taking −1 now, e.g., adding the node e to the subgraph of {a, b, c, d} leads a mutual-determination of {d, e} in Figure 1 and the above subgraph in Figure 3 also show this process. Then, mutual-determination of the new added i with the original positively frozen node j is formed.
• Case B: there are more than two neighbors which are positively frozen.
In case B, energy increase is unavoidable when node i is added. To obtain a coverage of the new graph G ′ from the original one G, the new added node i must be covered without other choice. Then, node i is negatively frozen. (There will be a supplementary and additional adjustment for this case in the following case E when the positively frozen neighbors have some common properties.) • Case C: there is no neighbor which is positively frozen, but all the unfrozen neighbors can take spin value −1 simultaneously.
In case C, energy increase is avoidable when node i is added, and the new added node i should be uncovered. When σ i takes value +1, all the unfrozen neighbors should take −1 simultaneously. Then, by the mutual-determinations and coverage of each edge in the reduced solution graph S(G), that these unfrozen neighbors change to be negatively frozen will lead a number of associated unfrozen nodes to be frozen.
• Case D: there is at least one pair of unfrozen neighbors that can not take spin value −1 simultaneously.
In case D, as the two neighbors can not take −1 simultaneously, energy increase is inevitable. Then, the new added variable i should take −1 to ensure the coverage. However, for the incompatible cycles (like that in the below subgraph of Figure 3), making any other node except i frozen to −1 and the rest unfrozen nodes connected by alternatively existing double edges will have the same effect and ensure the coverage. Thus, in case D freezing the new added node i to −1 will reduce the whole solution space to a partial solution subspace.
Nevertheless, as takeing any one to be frozen on the incompatible cycle leads to a solution subspace with the same size, we have the convenient way to make i negative backbone.
By the above analysis, the incompatible cycle in the reduced solution graph makes a possible inaccurate choice of the negatively frozen backbone. Thus, the hardness of solving Vertex-cover mainly stems from the incompatible cycles.
There exists an interesting entanglement between case A and case C. In case C, some added node i 1 has a positively frozen state, its unfrozen neighbors are forced to be frozen with some associated nodes. In case A, if some new added node i 2 is connected to i 1 and forms mutual-determination with i 1 by the rule of case A, the nodes that have been frozen by i 1 should be released to their original unfrozen state. To fulfill this releasing steps, an additional mark should be sticken to the node number, e.g., a node (4, 7) means that the node 4 has been frozen by the operation of adding node 7. Indeed, this freezing influence happens only in case C with node 7 positively frozen. Then, if the state of node 7 is changed to be unfrozen by adding a new node 8 in case A, we can release all the nodes with mark ( * , 7) and change the corresponding numbers to ( * , 0), in which 0 means the state of the node is unfrozen. This operation is named releasing operation.
For the releasing operation, there is a special case should be considered for the node adding process: • Case E: there are more than two neighbors which are positively frozen and have the same additional mark, and the unfrozen neighbors can take spin value −1 simultaneously.
This case is a supplementary and additional adjustment of case B.
In this case, the current node should form mutual-determinations with the positively frozen nodes whose additional marks are the same, and the releasing operation is operated for these positively frozen neighbors (a simple example can be seen in the below subgraph of Figure 7).

Some supplementing techniques for the states evolution
In the releasing operation for case A, to avoid some possible mistakes, a checking technique should be considered. When releasing the negatively frozen backbones in the releasing operations for case A, its local environment should be considered, and if there are positively frozen neighbors for the current negatively frozen backbone whose additional mark is not same as itself, the releasing process should be stopped (e.g., the node b in the process of subgraphs (3)(4) in Figure 2).
Be specific to this checking item, after the operations of case A-D, a rechecking technique additional mark with it (e.g., the node b in the process of subgraphs (4)(5) in Figure 2).
At last, by the process of above analysis, a complicated structure-odd cycles on the reduced solution graph could come into appearance, which makes conflictions for the relations among the unfrozen nodes. For the example in Figure 2, the subgraphs (1-7) provide the process from the original graph to the reduced solution graph by adding the nodes one by one using our techniques above, but unfortunately the unfrozen nodes b, c, d, e, f, g, h in subgraph (7) form an odd cycle. In the odd cycle, we find that any node except b taking any value will force the node b to be negatively frozen, and it is an incompatible cycle. To break this disharmony, the only way is to change the state of b to be negative backbone and make corresponding changes for its neighbors with lower ranks (e.g., the process from subgraph (7) to (8) in Figure 2). This technique is named odd cycles breaking.

Global characteristics of mutual-determinations
In the following, we will have an explicit discussion of the mutual-determinations and unfrozen nodes structure of Vertex-cover. As mentioned above, if some node i forms mutualdetermination with a node j, i.e., σ i = −1 forces σ j to take +1, correspondingly by the Vertex-cover, we have that σ i = +1 requires σ j = −1 to satisfy the coverage. If a node j forms a mutual-determination chain with some other nodes j 0 , j 1 , · · · , j k , a possible way is that the edges (j, j 0 ), (j 1 , j 2 ), · · · on the reduced solution graph are all double edges, i.e., all these pairs of nodes form mutual-determinations, which is shown in the Cycle 2-Compatible Cycle in Figure 3. When the node j takes vale −1 (covered), the nodes j 0 , j 2 , · · · , j 2l , · · · must take +1 by the mutual-determination relations and coverage of the edges connecting them, and the nodes j 1 , j 3 , · · · , j 2l+1 , · · · must take −1. Therefore, the alternatively existing double edges on the reduced solution graph lead to the emergence of the strong correlation for nodes of long distance.
Without confusion, we neglect the backbones in the reduced solution graph but keep the the increasing of the number of nodes and edges, the unfrozen nodes with double edges in the reduced solution graph may connect together, and form cycles and even giant connected component. Especially, for random graphs, the cycles connected by unfrozen nodes in the reduced solution graph must be with size of O(logN). Therefore, if the unfrozen nodes connect together to form a giant connected component [28], some of them taking value −1 will cause a percolation phenomenon [27] that many other nodes (O(N)) in this giant connected component will be forced to be frozen. As a result, the long-range correlation phenomenon emerges. In the work of Zhou [18], the long-range correlation of Vertex-cover for random graph appears at c = e. Indeed, by the literature of statistical mechanics, the existence of long-range correlation has close connection with the replica symmetric breaking of the solution space. As the correlation is formed by mutual-determinations, the long-range correlation can also provide an explicit explanation of the clustering phenomenon of solution space.
By the emergency of the long-range correlation nodes, the local environment becomes much more complicated. As unfrozen neighbors of the new added node i can be connected together by other unfrozen nodes, their values can not be assigned arbitrarily. In Figure   3, a schematic view of the compatible and incompatible cycles of unfrozen nodes is shown.
In Cycle 1, the unfrozen nodes k 1 , k 2 are connected by unfrozen nodes with alternatively existing double edges, and it is easy to find that the nodes k 1 , k 2 form a long-range correlation relation and can not take spin value −1 simultaneously. To the contrary, in the compatible Cycle 2, though the relation between j, j m−1 is also long-range correlation, they can take spin value −1 simultaneously by the mutual-determination chain in Cycle 2.

MUTUAL-DETERMINATION AND BACKBONE EVOLUTION ALGORITHM FOR VERTEX-COVER
In this section, we will introduce an algorithm for solving Vertex-cover based on case A-E and the node ranks. By the analysis in case A, B, C, D, E, we consider to update the state of the original graph G(N − 1) after adding a new node i. As the node states are classified by mutual-determinations and backbones, we can get an algorithm to find the reduced solution graph R(G) of Vertex-cover, this algorithm is named Mutual-determination and Backbone Evolution Algorithm, shown as follows: Let's take G[v] as an induced subgraph of original graph G by adding node v and To reflect the solution space structures of Vertex-cover, the ratios of negatively frozen backbone and positively frozen backbones are detected by the algorithm, in which one is monotone increasing and the other is monotone decreasing. In Figure 4, the ratios of the backbones are shown by the solid triangles, and the unfrozen nodes have its ratio with the residual part of one. Our results on the frozen nodes in one macroscopic state is higher than that in [17] mainly be the freezing influence. Besides, in Figure 5, the coverage of the Vertexcover which is the size of the minimal vertex-cover is approximated by our algorithm, which is Evolution Algorithm when c < e in the next section, our numerical results should be exact ones for the corresponding interval on random graphs.
As a comparison to the complete algorithm and the exact coverage, some experiments are made to verify the performance of the Mutual-determination and Backbone Evolution Algorithm which is an incomplete algorithm. In Figure 6, average Error of minimal vertex cover between experimental and exact results are plotted to provide the difference between the exact results and our results on the coverage, and it is evident to see that these differences are not very big and have their scales no more than 0.04 for c = 2, 4, 6 with increasing sizes.

Mutual-determination and Backbone Evolution Algorithm on some examples
To detect the reduced solution graph and provide a primary analysis of efficiency of our algorithm on the leaf-removal core, we will discuss the Vertex-cover on the complete graphs and cycles with even number of nodes for inspiration.
For the complete graphs, the process of our algorithm to obtain the reduced solution graph is rather simple: when the second node is added with an edge (subgraph (1) in Figure 7), the mutual-determination emerges; for the following added nodes, their local environment satisfies the case D and they can only be negative backbones. This process is shown in Figure 7 by a typical graph K 5 . It is easy to know that for the complete graph K N there must be N − 1 nodes be covered, and our results of reduced solution graph correspond to a solution subspace of the Vertex-cover of K N . The whole solution space possesses N solutions and by our algorithm we can obtain 2 solutions. Therefore, the mutual-determination and Backbone Evolution Algorithm is an incomplete algorithm for the solution space, but it may be efficient for finding one solution of Vertex-cover. Certainly, as analyzed in the above section, the incompatible cycles of the unfrozen node will bring the intrinsic difficulty for solving it and our algorithm can only obtain some approximated solutions for the original problem.
Then, the cycles C 2N with even number of nodes are considered. The process of our algorithm to obtain its reduced solution graph is a regular process: when odd number of nodes are added, there are no unfrozen nodes in the reduced solution graph; when even number of nodes are added, the releasing operations should be considered and all the nodes are unfrozen with double edges/mutual-determinations alternatively connected together; for the last node, it connects with two positively frozen nodes which have the same additional mark 2N − 1, and by the case E the last node forms mutual-determination with node 2N − 1 and the rest are released. The whole process is schematically shown in the lower subgraphs (a − d) in Figure 7 by a typical graph C 4 . Thus, the solution space of C 2N can be obtained, and it is easy to verify that the result is strict by our algorithm.

ANALYSIS OF MUTUAL-DETERMINATION AND BACKBONE EVOLUTION ALGORITHM FOR VERTEX-COVER
The Mutual-determination and Backbone Evolution Algorithm aims to obtain the whole solution space, and it is easy to find that it is an algorithm of polynomial time. As the Vertexcover problem is a typical NP-complete problem, this algorithm can not be a complete one and will lose its efficiency in some case. In this section, some detailed analysis on the algorithm will be provided.

The time complexity of Mutual-determination and Backbone Evolution Algorithm
By the algorithm in the above section, the process of determining the ranks of the nodes in the graph is intrinsically a leaf removal process, and it will cost at most O(N) steps to obtain the whole ranks of all the nodes.
By considering the nodes sequentially according to their ranks, when adding a new node to the original graph, first we should consider its local environment, which will cost at most constant C steps for random graph. Then, in different cases A-E, there may be additional time cost. In case B and D, the current state of the new added node is only determined by its neighbors and it causes no influence to others; In case C, the freezing of the current node will cause an influence to the unfrozen neighbors and those related to them, and thus the At last, considering case D, when the leaf-removal core is null, this case can be reduced to the odd cycle breaking, and it will bring the kernel difficulty when the leaf-removal core exists.
Therefore, the reduced solution graph obtained by our algorithm can reveals the exact solution space when there is no leaf-removal core.
By the above analysis, we have shown that the Mutual-determination and Backbone

22
Evolution Algorithm is strict when there is no leaf-removal core in the graph. By the results in [29], there is no leaf-removal core in the random graph with high probability when the average degree c is less than e. Then, our algorithm is strict with high probability when c < e.

Cycles in the reduced solution graph
The even and odd cycles of unfrozen nodes will be analyzed in this subsection. In this right subgraph of Figure  determinations, e.g., subgraph (7) of Figure 2, what we can do is to perform the odd cycle breaking, which keeps the strictness of our algorithm.
Unfortunately, there is the other way to produce an odd cycle of alternative mutualdeterminations, just like the Incompatible Cycle in the below subgraph of Figure 3. This kind of odd cycle structure emerges when the leaf-removal core exists and is hard to be broken for the lowest energy configuration of Vertex-cover. As the incompatible cycle brings obstacle for obtaining the real reduced solution graph, changing any unfrozen node on it to be negatively frozen is a possible choice for the reduced solution graph. In our algorithm, we can only choose one way to proceed, which makes the solution space collapse to a subspace.
Many steps of the collapsing may lead to unnecessary energy increase and superfluous cover of the graph.
In fact, we can keep all the incompatible cycles of alternative mutual-determinations without breaking choices for each step in the leaf-removal core and deal with them for the final reduced solution graph. All the backbones have no influence on the solution space, but breaking the incompatible cycles of alternative mutual-determinations on the reduced solution graph is an urgent task for achieving the proper solution subspaces. Many these incompatible cycles are coupled together and should be broken by making some nodes on 23 them negatively frozen. The fewer the number of negatively frozen nodes are chosen, the better covers we can obtain. Therefore, this problem can be reduced to the MAX-CUT [30] problem for the unfrozen nodes of the reduced solution graph. By the results of MAX-CUT, breaking the edges of unfrozen nodes which do not belong to the max-cut will lead to totaly compatible cycles. However, the MAX-CUT problem is also a NP-complete problem which is hard to solve.

CONCLUSION AND DISCUSSION
A new solution space structure, mutual-determination between unfrozen nodes is defined and discovered in some detailed case of the Vertex-cover. Based on the mutualdeterminations and backbones, we construct the reduced solution graph to reveal the solution space of Vertex-cover. And, inspired by the leaf removal process and introducing node ranks, a dynamical process for the evolution of the node states is studied to achieve the current states of nodes in the reduced solution graph. Combing the mutual-determinations, backbones and the node ranks, an algorithm named Mutual-determination and Backbone Evolution Algorithm is proposed to obtained the accurate reduced solution graph. To ensure the accuracy of the algorithm, the releasing operations, checking and rechecking techniques and odd cycles breaking operation are defined by considering the influence propagation.
Then, the numerical results and some examples are given to verify the validity of the algorithm. Besides, we have proved that this algorithm is an O(N 2 ) algorithm and performs strict when there is no leaf-removal core for the graph. the influence of incompatible cycles of unfrozen nodes to the algorithm is given, which can be reduced to MAX-CUT problem.
The Mutual-determination and Backbone Evolution Algorithm can be applied to a wide range of graphs. Though the difficulties are brought to by the incompatible cycles in case D on the reduced solution graph, choosing proper strategies to break the cycles will be helpful to obtain a solution subspace, which will be beneficial to solve the Vertex-cover problem in different topologies. Besides, in order to break the incompatible cycles of unfrozen nodes in case D on the reduced solution graph, we should design better heuristic strategies to check the key unfrozen nodes on it, such as taking advantage of the centrality or clustering coefficient [33,34]. However, as the intrinsic character of Vertex-cover is NP-complete, the Mutual-determination and Backbone Evolution Algorithm will still be an approximated one, and what we aim at is to improve the accuracy of solving different graphs of Vertex-cover.
The reduced solution graph of Mutual-determination and Backbone Evolution Algorithm can correspond to the whole solution space of Vertex-cover in some cases, which is a great help to count the number of solutions. Similar as the #CSP [31,32], the #Vertex-cover can be analyzed based on the reduced solution graph. However, calculating the exact entropy of the solution space needs a much detailed analysis of the constructions of the reduced solution graph and there should be many techniques to be introduce on counting the solutions on the reduced solution graph. Besides, the reduced solution graph can help explicitly determine the role of every node and calculate the partition functions and marginal probabilities of the nodes/variables. Some of the related results will be proceeded in our future work.
The principal of our algorithm is related to the replica symmetry theory but not restrict to. Most of recent algorithms solving combinatorial optimization problems always concentrate to find one solution, such as the searching algorithms, heuristic algorithms and even the Belief/Survey Propagation algorithm [15,21]. They assign values to the nodes/variables according to some strategies and do backtracking to reach the optimal solution, or determine