Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2012-01-09
Physics
Condensed Matter
Disordered Systems and Neural Networks
4 pages, 3 figures
Scientific paper
We study the vertex-cover problem which is an NP-hard optimization problem and a prototypical model exhibiting phase transitions on random graphs, e.g., Erdoes-Renyi (ER) random graphs. These phase transitions coincide with changes of the solution space structure, e.g, for the ER ensemble at connectivity c=e=2.7183 from replica symmetric to replica-symmetry broken. For the vertex-cover problem, also the typical complexity of exact branch-and-bound algorithms, which proceed by exploring the landscape of feasible configurations, change 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.
Dewenter Timo
Hartmann Alexander K.
No associations
LandOfFree
Phase transition for cutting-plane approach to vertex-cover problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Phase transition for cutting-plane approach to vertex-cover problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase transition for cutting-plane approach to vertex-cover problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-643625