For two-community stochastic block models, the minimum vertex cover problem becomes hard when in-degree plus out-degree exceeds e, but becomes easy again when cross-community degree is large enough.
Two faces of greedy leaf removal procedure on graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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\"{o}s-R\'{e}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.
fields
cond-mat.stat-mech 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Statistical mechanics of the minimum vertex cover problem in stochastic block models
For two-community stochastic block models, the minimum vertex cover problem becomes hard when in-degree plus out-degree exceeds e, but becomes easy again when cross-community degree is large enough.