  The phase-transition behavior of the NP-hard vertex-cover (VC) combinatorial
optimization problem is studied numerically by linear programming (LP) on
ensembles of random graphs. As the basic Simplex (SX) algorithm suitable for
such LPs may produce incomplete solutions for sufficiently complex graphs, the
application of cutting-plane (CP) methods is sought. We consider Gomory and
{0,1/2} cuts. We measure the probability of obtaining complete solutions with
these approaches as a function of the average node degree c and observe
transition between typically complete and incomplete phase regions. While not
generally complete solutions are obtained for graphs of arbitrarily high
complexity, the CP approaches still advance the boundary in comparison to the
pure SX algorithm, beyond the known replica-symmetry breaking (RSB) transition
at c=e=2.718... . In fact, our results provide evidence for another algorithmic
transition at c=2.90(2).
  Besides this, we quantify the transition between easy and hard solvability of
the VC problem also in terms of numerical effort. Further we study the
so-called whitening of the solution, which is a measure for the degree of
freedom that single vertices experience with respect to degenerate solutions.
Inspection of the quantities related to clusters of white vertices reveals that
whitening is affected, only slightly but measurably, by the RSB transition.
