Long-range frustration in minimal vertex cover problem on random graphs

A vertex cover on a graph is a set of vertices in which each edge of the graph is adjacent to at least one vertex in the set. The minimal vertex cover (MVC) problem concerns finding vertex covers with the smallest cardinality, which is a typical computationally hard problem among combinatorial optimization on graphs. Here, we follow the idea of the long-range frustration (LRF) in MVC configurations proposed in Zhou (2005 Phys. Rev. Lett. 94 217203). We correct its analytical framework and further extend it from Erdös-Rényi random graphs to general random graphs. We formulate the framework of LRF into a percolation model, and analytically estimate the energy density of MVCs on uncorrelated random graphs only with their degree distributions. We test our framework on some typical random graph models along with other methods, such as a hybrid algorithm of greedy leaf removal (GLR) procedure combined with survey propagation-guided decimation (SPD) algorithm and an analytical theory based on the GLR procedure which ignores LRF effect. We show that, when there is a percolation of LRF effect, the above three predictions of energy density, say (Formula presented) (Formula presented), (Formula presented) (Formula presented), and (Formula presented) (Formula presented), follow a scenario as (Formula presented) (Formula presented) in most cases and (Formula presented) (Formula presented) in the other cases, and (Formula presented) (Formula presented) is much closer to (Formula presented) (Formula presented) than (Formula presented) (Formula presented) as (Formula presented) (Formula presented). Our results show that LRF is a proper mechanism for the formation of complex energy landscape in the MVC problem and a theoretical framework of LRF helps to characterize its ground-state properties.