Dewenter Timo, Hartmann Alexander K
Institut für Physik, Universität Oldenburg, D-26111 Oldenburg, Germany.
Phys Rev E Stat Nonlin Soft Matter Phys. 2012 Oct;86(4 Pt 1):041128. doi: 10.1103/PhysRevE.86.041128. Epub 2012 Oct 15.
We study the vertex-cover problem, which is a nondeterministic polynomial-time hard optimization problem and a prototypical model exhibiting phase transitions on random graphs, such as Erdős-Rényi (ER) random graphs. These phase transitions coincide with changes of the solution space structure, e.g., for the ER ensemble at connectivity c=e≈2.7183 from replica symmetric to replica-symmetry broken. For the vertex-cover problem, the typical complexity of exact branch-and-bound algorithms, which proceed by exploring the landscape of feasible configurations, also changes close to this phase transition from "easy" to "hard." In this work, we consider an algorithm which has a completely different strategy: The problem is mapped onto a linear programming problem augmented by a cutting-plane approach; hence the algorithm operates in a space outside the space of feasible configurations until the final step, where a solution is found. Here we show that this type of algorithm also exhibits an easy-hard transition around c=e, which strongly indicates that the typical hardness of a problem is fundamental to the problem and not due to a specific representation of the problem.
我们研究顶点覆盖问题，它是一个非确定性多项式时间难优化问题，也是一个在随机图（如厄多斯 - 雷尼（ER）随机图）上展现相变的典型模型。这些相变与解空间结构的变化一致，例如，对于连通性(c = e\approx2.7183)的ER系综，从复制对称到复制对称破缺。对于顶点覆盖问题，通过探索可行配置格局来进行的精确分支定界算法的典型复杂度，在接近这个相变时也从“容易”变为“困难”。在这项工作中，我们考虑一种具有完全不同策略的算法：该问题被映射到一个通过割平面方法增强的线性规划问题；因此，该算法在可行配置空间之外的空间中运行，直到最后一步找到解。在这里我们表明，这种类型的算法在(c = e)附近也表现出易 - 难转变，这强烈表明一个问题的典型难度是该问题的基本属性，而非源于该问题的特定表示形式。
