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

Yu-Tao Li, Chun-Yan Zhao, Jin-Hua Zhao

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 findin…