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"{o}s-R'{e}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 \ldots$. 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_{\mathrm{i}\mathrm{n}}$ and $c_{\mathrm{o}\mathrm{u}\mathrm{t}}$, respectively. Our analysis based on the cavity method indicates that the solution search becomes difficult when $c_{\mathrm{i}\mathrm{n}}+c_{\mathrm{o}\mathrm{u}\mathrm{t}}>e$, but becomes easy again when $c_{\text{out}}$ is sufficiently larger than $c_{\mathrm{i}\mathrm{n}}$ in the region $c_{\mathrm{o}\mathrm{u}\mathrm{t}}>e$. Experiments based on various search algorithms support the theoretical prediction.