Statistical mechanics of the minimum vertex cover problem in stochastic block models
arXiv:1908.07234 · doi:10.1103/PhysRevE.100.062101
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 exhibits computational difficulty in searching the Min-VC set above a critical point . 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 and , respectively. Our analysis based on the cavity method indicates that the solution search becomes difficult when , but becomes easy again when is sufficiently larger than in the region . Experiments based on various search algorithms support the theoretical prediction.
arXiv comment10 pages, 8 figures
References in corpus (15)
- Ising formulations of many NP problems
- The performance of modularity maximization in practical contexts
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Core percolation on complex networks
- Immunization of Real Complex Communication Networks
- Message passing for vertex covers
- Generalization of core percolation on complex networks
- Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
- Statistical Mechanics of the Hyper Vertex Cover Problem
- Distributed Vertex Cover Algorithms For Wireless Sensor Networks
- Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
- Statistical physics of hard combinatorial optimization: The vertex cover problem
- Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
- 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