Regensburg 2004 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

DY: Dynamik und Statistische Physik

DY 26: General Statistical Physics

DY 26.3: Talk

Tuesday, March 9, 2004, 17:15–17:30, H2

Ground-state structure of the vertex-cover problem — •Wolfgang Barthel and Alexander K. Hartmann — Institute for Theoretical Physics, Göttingen

Hard combinatorical optimization problems play an important role in Theoretical Computer Science. One is especially interested in the time complexity of such problems, i. e. how fast a typical instance can be solved depending on its size. It is expected that this is strongly connected to the landscape of the ground state structure of this problems. Here we consider the vertex-cover problem: Take a random graph consisting of undirected edges that meet at vertices and put guards on the vertices such that there is one at at least one endpoint of every edge. Solutions are covers which need a minimal number of guards and usually there is an exponential number of them. We numerically analyze the landscape of the solution space. A change in the ground state structure is observed at the point where all known fast algorithms fail.