Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking

Abstract

Leaf-Removal process has been widely researched and applied in many mathematical and physical fields to help understand the complex systems, and a lot of problems including the minimal 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 minimal vertex-cover problem into the Leaf-Removal cores breaking process and maximal matching of the remained graphs, it is proved that any minimal vertex-covers of the whole graph can be located into these two processes, of which the latter one is a P problem, 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 existing node importance measurements, and compared with the exact minimal 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 help understand some NP problems.

11pages, 6 figures, 2 tables

References in corpus (13)

• Error and attack tolerance of complex networks
• Identification of influential spreaders in complex networks
• Breakdown of the Internet under intentional attack
• Influence maximization in complex networks through optimal percolation
• k-core organization of complex networks
• Spectral redemption: clustering sparse networks
• Percolation on sparse networks
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Immunization of Real Complex Communication Networks
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Message passing for vertex covers
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones