Weigt M, Hartmann A K
Institute for Theoretical Physics, University of Göttingen, Bunsenstrasse 9, 37073 Göttingen, Germany.
Phys Rev Lett. 2001 Feb 19;86(8):1658-61. doi: 10.1103/PhysRevLett.86.1658.
We analytically describe the typical solution time needed by a backtracking algorithm to solve the vertex-cover problem on finite-connectivity random graphs. We find two different transitions: The first one is algorithm dependent and marks the dynamical transition from linear to exponential solution times. The second one gives the maximum computational complexity, and is found exactly at the threshold where the system undergoes an algorithm-independent phase transition in its solvability. Analytical results are corroborated by numerical simulations.
我们通过分析描述了回溯算法在有限连通性随机图上解决顶点覆盖问题所需的典型求解时间。我们发现了两种不同的转变：第一种转变依赖于算法，标志着从线性求解时间到指数求解时间的动态转变。第二种转变给出了最大计算复杂度，并且恰好在系统在可解性方面经历与算法无关的相变的阈值处找到。数值模拟证实了分析结果。
