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...

Full description

Saved in:
Bibliographic Details
Published in:Computer physics communications 2005-07, Vol.169 (1), p.234-237
Main Authors: Hartmann, Alexander K., Barthel, Wolfgang, Weigt, Martin
Format: Article
Language:English
Subjects:
Combinatorial optimization
NP-complete
Phase transitions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0010-4655
1879-2944
DOI:10.1016/j.cpc.2005.03.054