Hits:

Indexed by:期刊论文

Date of Publication:2015-04-01

Journal:JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT

Included Journals:SCIE、Scopus

Volume:2015

Issue:4

ISSN No.:1742-5468

Key Words:classical phase transitions (theory); phase diagrams (theory); cavity and replica method; disordered systems (theory)

Abstract: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.