Organization mechanism and counting algorithm on vertex-cover solutions

Counting the solution number of combinational optimization problems is an important topic in the study of computational complexity, which is concerned with Vertex-Cover in this paper. First, we investigate organizations of Vertex-Cover solution spaces by the underlying connectivity of unfrozen vertices and provide facts on the global and local environment. Then, a Vertex-Cover Solution Number Counting Algorithm is proposed and its complexity analysis is provided, the results of which fit very well with the simulations and have a better performance than those by 1-RSB in the neighborhood of c=e for random graphs. Based on the algorithm, variation and fluctuation on the solution number the statistics are studied to reveal the evolution mechanism of the solution numbers. Furthermore, the marginal probability distributions on the solution space are investigated on both the random graph and scale-free graph to illustrate the different evolution characteristics of their solution spaces. Thus, doing solution number counting based on the graph expression of the solution space should be an alternative and meaningful way to study the hardness of NP-complete and #P-complete problems and the appropriate algorithm design can help to achieve better approximations of solving combinational optimization problems and the corresponding counting problems.