Department of Mathematical and Computing Science, Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan.
Phys Rev E. 2019 Dec;100(6-1):062101. doi: 10.1103/PhysRevE.100.062101.
The minimum vertex cover (Min-VC) problem is a well-known NP-hard problem. Earlier studies illustrate that the problem defined over the Erdös-Rényi random graph with a mean degree c exhibits computational difficulty in searching the Min-VC set above a critical point c=e=2.718.... Here, we address how this difficulty is influenced by the mesoscopic structures of graphs. For this, we evaluate the critical condition of difficulty for the stochastic block model. We perform a detailed examination of the specific cases of two equal-size communities characterized by in and out degrees, which are denoted by c_{in} and c_{out}, respectively. Our analysis based on the cavity method indicates that the solution search once becomes difficult when c_{in}+c_{out} exceeds e from below, but becomes easy again when c_{out} is sufficiently larger than c_{in} in the region c_{out}>e. Experiments based on various search algorithms support the theoretical prediction.
最小顶点覆盖（Min-VC）问题是一个著名的 NP 难问题。早期的研究表明，在平均度数为 c 的 Erdős-Rényi 随机图上定义的问题，在一个关键点 c=e=2.718……之上搜索 Min-VC 集时存在计算困难。在这里，我们研究了这种困难是如何受到图的中间尺度结构的影响的。为此，我们评估了随机块模型的困难临界条件。我们对由内度和外度分别表示为 c_{in}和 c_{out}的两个等大小社区的特定情况进行了详细的考察。我们基于腔方法的分析表明，当 c_{in}+c_{out}从下方超过 e 时，解的搜索就变得困难，但当 c_{out}在 c_{out}>e 的区域中足够大于 c_{in}时，搜索又变得容易了。基于各种搜索算法的实验支持了理论预测。
