Ground-state entropy of the random vertex-cover problem

Counting the number of ground states for a spin-glass or nondeterministic polynomial-complete combinatorial optimization problem is even more difficult than the already hard task of finding a single ground state. In this paper the entropy of minimum vertex covers of random graphs is estimated through a set of iterative equations based on the cavity method of statistical mechanics. During the iteration both the cavity entropy contributions and cavity magnetizations for each vertex are updated. This approach overcomes the difficulty of iterative divergence encountered in the zero-temperature first-step replica-symmetry-breaking (1RSB) spin-glass theory. It is still applicable when the 1RSB mean-field theory is no longer stable. The method can be extended to compute the entropies of ground states and metastable minimal-energy states for other random-graph spin-glass systems.

Figure 1

(Color online) Ground-state entropy density of the vertex-cover problem as a function of the mean vertex degree $c$ of the random graph. Circles are simulation data [11]; up and down triangles are, respectively, theoretical results obtained by the replica-symmetric and the 1RSB cavity methods. The finite-temperature entropy density values at $T=0.091$ and 0.04 are also shown as a comparison.

Figure 2

Predicted mean ground-state entropy of the random vertex-cover problem at connectivity $c=10$ as a function of the cutoff parameter $ϵ$.