Statistical mechanics of the minimum vertex cover problem in stochastic block models

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.