Statistical mechanics of the vertex-cover problem

Details Statistical mechanics of the vertex-cover problem Statistical mechanics of the vertex-cover problem

2003-07-10

arxiv.org/abs/cond-mat/0307236v1

J. Phys. A: Math. Gen. 36, 11069 (2003)

Physics

Condensed Matter

Disordered Systems and Neural Networks

review article, 26 pages, 9 figures, to appear in J. Phys. A: Math. Gen

Scientific paper

10.1088/0305-4470/36/43/028

We review recent progress in the study of the vertex-cover problem (VC). VC belongs to the class of NP-complete graph theoretical problems, which plays a central role in theoretical computer science. On ensembles of random graphs, VC exhibits an coverable-uncoverable phase transition. Very close to this transition, depending on the solution algorithm, easy-hard transitions in the typical running time of the algorithms occur. We explain a statistical mechanics approach, which works by mapping VC to a hard-core lattice gas, and then applying techniques like the replica trick or the cavity approach. Using these methods, the phase diagram of VC could be obtained exactly for connectivities $ce$, the solution of VC exhibits full replica symmetry breaking. The statistical mechanics approach can also be used to study analytically the typical running time of simple complete and incomplete algorithms for VC. Finally, we describe recent results for VC when studied on other ensembles of finite- and infinite-dimensional graphs.

Affiliated with

Also associated with

No associations

Rating

Statistical mechanics of the 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 Statistical mechanics of the vertex-cover problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical mechanics of the vertex-cover problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137295