We study the vertex-cover problem, which is a nondeterministic polynomial-time hard optimization problem and a prototypical model exhibiting phase transitions on random graphs, such as Erdős-Rényi (ER) random graphs. These phase transitions coincide with changes of the solution space structure, e.g., for the ER ensemble at connectivity $c=e\approx 2.7183$ from replica symmetric to replica-symmetry broken. For the vertex-cover problem, the typical complexity of exact branch-and-bound algorithms, which proceed by exploring the landscape of feasible configurations, also changes close to this phase transition from “easy” to “hard.” In this work, we consider an algorithm which has a completely different strategy: The problem is mapped onto a linear programming problem augmented by a cutting-plane approach; hence the algorithm operates in a space outside the space of feasible configurations until the final step, where a solution is found. Here we show that this type of algorithm also exhibits an easy-hard transition around $c=e$, which strongly indicates that the typical hardness of a problem is fundamental to the problem and not due to a specific representation of the problem.

• Received 9 January 2012

DOI:https://doi.org/10.1103/PhysRevE.86.041128