  Vertex cover is one of the classical NP-complete problems in theoretical
computer science. A vertex cover of a graph is a subset of vertices such that
for each edge at least one of the two endpoints is contained in the subset.
When studied on Erdos-Renyi random graphs (with connectivity c) one observes a
threshold behavior: In the thermodynamic limit the size of the minimal vertex
cover is independent of the specific graph. Recent analytical studies show that
on the phase boundary, for small connectivities c<e, the system is replica
symmetric, while for larger connectivities replica symmetry breaking occurs.
This change coincides with a change of the typical running time of algorithms
from polynomial to exponential.
  To understand the reasons for this behavior and to compare with the
analytical results, we numerically analyze the structure of the solution
landscape. For this purpose, we have also developed an algorithm, which allows
the calculation of the backbone, without the need to enumerate all solutions.
We study exact solutions found with a Branch-and-Bound algorithm as well as
configurations obtained via a Monte Carlo simulation.
  We analyze the cluster structure of the solution landscape by direct
clustering of the states, by analyzing the eigenvalue spectrum of correlation
matrices and by using a hierarchical clustering method. All results are
compatible with a change at c=e. For small connectivities, the solutions are
collected in a finite small number of clusters, while the number of cluster
diverges slowly with system size for larger connectivities and replica symmetry
breaking, but not 1-RSB, occurs.
