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

DOI10.1088/1742-5468/AB25E1MaRDI QIDQ3303374zbMATH OpenOpenAlexFDO

Authors Wei Wei, Xing Li, Xiang-Nan Feng, Zhiming Zheng

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.05799

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Complexity and performance of numerical algorithms (65Y20)

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.

Recommendations

• A decomposition strategy for the vertex cover problem
• Vertex cover structural parameterization revisited
• scientific article; zbMATH DE number 1420918
• Vertex cover: Further observations and further improvements
• Vertex Cover Reconfiguration and Beyond
• Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Some results on incremental vertex cover problem
• Dominating vertex covers: the vertex-edge domination problem

Cites work

• Automorphic forms and geometry of arithmetic varieties
• Faster scaling algorithms for general graph matching problems
• Graph theory with applications
• scientific article; zbMATH DE number 3375418 (Why is no real title available?)
• Introduction to Applied Nonlinear Dynamical Systems and Chaos
• Networks
• Spectral redemption in clustering sparse networks
• Statistical and algebraic analysis of a family of random Boolean equations
• The centrality index of a graph
• Two solutions to diluted p-spin models and XORSAT problems

Cited in

(2)

• Two faces of greedy leaf removal procedure on graphs
• Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space

This page was built for publication: Core influence mechanism on vertex-cover problem through leaf-removal-core breaking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3303374)