Organization mechanism and counting algorithm on Vertex-Cover solutions

Abstract

Counting the solution number of combinational optimization problems is an important topic in the study of computational complexity, especially on the #P-complete complexity class. In this paper, we first investigate some organizations of Vertex-Cover unfrozen subgraphs by the underlying connectivity and connected components of unfrozen vertices. 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 better performance than those by 1-RSB in a neighborhood of c = e for random graphs. Base on the algorithm, variation and fluctuation on the solution number statistics are studied to reveal the evolution mechanism of the solution numbers. Besides, marginal probability distributions on the solution space are investigated on both random graph and scale-free graph to illustrate different evolution characteristics of their solution spaces. Thus, doing solution number counting based on graph expression of solution space should be an alternative and meaningful way to study the hardness of NP-complete and #P-complete problems, and appropriate algorithm design can help to achieve better approximations of solving combinational optimization problems and the corresponding counting problems.

arXiv comment17 pages, 6 figures

References in corpus (13)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Core percolation in random graphs: a critical phenomena analysis
• Immunization of Real Complex Communication Networks
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Message passing for vertex covers
• Computational complexity arising from degree correlations in networks
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Ground-State Entropy of the Random Vertex-Cover Problem
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• Analysis on the evolution process of BFW-like model with explosive percolation of multiple giant components