Phase transition and finite-size scaling in the vertex-cover problem

NP-complete problems play a fundamental role in theoretical computer science. Recently, phase transitions were discovered in such problems, when studying suitably parameterized random ensembles. By applying concepts and methods from statistical physics, it is possible to understand these models and the phase transitions which occur. Here, we consider the vertex-cover problem, one of the six "basic" NP-complete problems. We describe the phase transition and the running time of an exact algorithm around the phase transition. To investigate how this transition resembles a phase transition in physical systems, we apply finite-size scaling and we study a correlation-length like quantity. (c) 2005 Elsevier B.V. All rights reserved.