  The distribution of the computational cost of linear-programming (LP)
relaxation for vertex cover problems on Erdos-Renyi random graphs is evaluated
by using the rare-event sampling method. As a large-deviation property,
differences of the distribution for "easy" and "hard" problems are found
reflecting the hardness of approximation by LP relaxation. In particular, by
evaluating the total variation distance between conditional distributions with
respect to the hardness, it is suggested that those distributions are almost
indistinguishable in the replica symmetric (RS) phase while they asymptotically
differ in the replica symmetry breaking (RSB) phase. In addition, we seek for a
relation to graph structure by investigating a similarity to bipartite graphs,
which exhibits a quantitative difference between the RS and RSB phase. These
results indicate the nontrivial relation of the typical computational cost of
LP relaxation to the RS-RSB phase transition as present in the spin-glass
theory of models on the corresponding random graph structure.
