Hierarchical Decomposition Mechanism by König-Egérvary Layer-Subgraph with Application on Vertex-Cover
König-Egérvary (KE) graph and theorem provides useful tools and deep understanding in the graph theory, which is an essential way to model complex systems. KE properties are strongly correlated with the maximum matching problem and minimum vertex cover problem, and have been widely researched and applied in many mathematical, physical and theoretical computer science problems. In this paper, based on the structural features of KE graphs and applications of maximum edge matching, the concept named KE-layer structure of general graphs is proposed to decompose the graphs into several layers. To achieve the hierarchical decomposition, an algorithm to verify the KE graph is given by the solution space expression of Vertex-Cover, and the relation between multi-level KE graphs and maximal matching is illustrated and proved. Furthermore, a framework to calculate the KE-layer number and approximate the minimal vertex-cover is proposed, with different strategies of switching nodes and counting energy. The phase transition phenomenon between different KE-layers are studied with the transition points located, the vertex cover numbers got by this strategy have comparable advantage against several other methods, and its efficiency outperforms the existing ones just before the transition point. Also, the proposed method performs stability and satisfying accuracy at different scales to approximate the exact minimum coverage. The KE-layer analysis provides a new viewpoint to understand the structural organizations of graphs better, and its formation mechanism can help reveal the intrinsic complexity and establish heuristic strategy for large-scale graphs/systems recognition.
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, 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.