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

Abstract

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

10 pages, 8 figures

References in corpus (8)

• Core percolation on complex networks
• Immunization of Real Complex Communication Networks
• Message passing for vertex covers
• Generalization of core percolation on complex networks
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Two faces of greedy leaf removal procedure on graphs