Two faces of greedy leaf removal procedure on graphs
arXiv:1809.05843 · doi:10.1088/1742-5468/ab2cca
Abstract
The greedy leaf removal (GLR) procedure on a graph is an iterative removal of any vertex with degree one (leaf) along with its nearest neighbor (root). Its result has two faces: a residual subgraph as a core, and a set of removed roots. While the emergence of cores on uncorrelated random graphs was solved analytically, a theory for roots is ignored except in the case of Erdös-Rényi random graphs. Here we analytically study roots on random graphs. We further show that, with a simple geometrical interpretation and a concise mean-field theory of the GLR procedure, we reproduce the zero-temperature replica symmetric estimation of relative sizes of both minimal vertex covers and maximum matchings on random graphs with or without cores.
arXiv comment39 pages, 5 figures, and 3 tables
References in corpus (44)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Error and attack tolerance of complex networks
- Assortative mixing in networks
- Cooperative Game Theory Approaches for Network Partitioning
- The diameter of the world wide web
- The large-scale organization of metabolic networks
- Random graphs with arbitrary degree distributions and their applications
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Critical phenomena in complex networks
- Universal Behavior of Load Distribution in Scale-free Networks
- k-core organization of complex networks
- Emergence of bimodality in controlling complex networks
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- On the Origins of Hierarchy in Complex Networks
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- The number of matchings in random graphs
- Predicting Positive and Negative Links in Online Social Networks
- Core percolation on complex networks
- Core percolation in random graphs: a critical phenomena analysis
- Articulation Points in Complex Networks
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Vertex cover problem studied by cavity method: Analytics and population dynamics
- Message passing for vertex covers
- Critical dynamics of the k-core pruning process
- Analytic solution of a static scale-free network model
- Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
- Statistical Mechanics of the Minimum Dominating Set Problem
- Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
- Statistical mechanics of the vertex-cover problem
- Core percolation and onset of complexity in Boolean networks
- Finite size corrections to disordered Ising models on Random Regular Graphs
- Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
- The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
- Computational core and fixed-point organisation in Boolean networks
- Statistical physics of hard combinatorial optimization: The vertex cover problem
- Ground-State Entropy of the Random Vertex-Cover Problem
- The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
- Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
- Kinked Entropy and Discontinuous Microcanonical Spontaneous Symmetry Breaking
- Typical Performance of Approximation Algorithms for NP-hard Problems