Takabe Satoshi, Hukushima Koji
Graduate School of Arts and Sciences, The University of Tokyo, 3-8-1 Komaba, Meguro-ku, Tokyo 153-8902, Japan.
Phys Rev E Stat Nonlin Soft Matter Phys. 2014 Jun;89(6):062139. doi: 10.1103/PhysRevE.89.062139. Epub 2014 Jun 27.
The minimum vertex-cover problems on random α-uniform hypergraphs are studied using two different approaches, a replica method in statistical mechanics of random systems and a leaf removal algorithm. It is found that there exists a phase transition at the critical average degree e/(α-1), below which a replica symmetric ansatz in the replica method holds and the algorithm estimates exactly the same solution of the problem as that by the replica method. In contrast, above the critical degree, the replica symmetric solution becomes unstable and the leaf-removal algorithm fails to estimate the optimal solution because of the emergence of a large size core. These results strongly suggest a close relation between the replica symmetry and the performance of an approximation algorithm. Critical properties of the core percolation are also examined numerically by a finite-size scaling.
利用两种不同方法研究了随机α-均匀超图上的最小顶点覆盖问题，一种是随机系统统计力学中的副本方法，另一种是叶移除算法。结果发现，在临界平均度e/(α - 1)处存在相变，低于该临界平均度时，副本方法中的副本对称假设成立，且该算法估计出的问题解与副本方法完全相同。相反，高于临界度时，副本对称解变得不稳定，由于出现了大尺寸核，叶移除算法无法估计出最优解。这些结果有力地表明了副本对称性与近似算法性能之间存在密切关系。还通过有限尺寸标度对核渗流的临界性质进行了数值研究。
