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

Abstract 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 x LRF , x GLR + SPD , and x GLR , follow a scenario as x LRF > x GLR + SPD > x GLR in most cases and x GLR + SPD > x LRF > x GLR in the other cases, and x LRF is much closer to x GLR + SPD than x GRL as |