Core influence mechanism on vertex-cover problem through leaf-removal-core breaking

Leaf-removal process has been widely researched and applied in many mathematical and physical fields to help understand the complex systems. A lot of problems including the minimum vertex-cover are deeply related to this process and the leaf-removal cores. In this paper, based on the structural features of the leaf-removal cores, a method named core influence is proposed to break the graphs into no-leaf-removal-core ones, which takes advantages of identifying some significant nodes by localized and greedy strategy. By decomposing the minimum vertex-cover problem into the leaf-removal core breaking process and maximal matching of the remaining graphs, it is proved that any minimum vertex-cover of the whole graph can be located into these two processes and the best boundary is achieved at the transition point. Compared with other node importance indices, the core influence method could break down the leaf-removal cores much faster and get the no-core graphs by removing fewer nodes from the graphs. Also, the vertex-cover numbers resulted from this method are lower than those of existing node importance measurements, and compared with the exact minimum vertex-cover numbers, this method performs appropriate accuracy and stability at different scales. This research provides a new localized greedy strategy to break the hard leaf-removal cores efficiently and heuristic methods could be constructed to promote the comprehension of the intrinsic hardness of NP problems. (paper: interdisciplinary statistical mechanics)