Spin-glass model for the C -dismantling problem
Shao-Meng Qin · Physical review. E · 2018
The $C$-dismantling (CD) problem aims at finding the minimum vertex set $\mathcal{D}$ of a graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ after removing which the remaining graph will break into connected components with the size not larger than $C$. In this paper, we introduce a spin-glass model with $C+1$ integer-value states into the CD problem and then study the properties of this spin-glass model with the belief-propagation (BP) equations under the replica-symmetry ansatz. We give the lower bound ${\ensuremath{\rho}}_{c}$ of the relative size of $\mathcal{D}$ with finite $C$ on regular random graphs and Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi random graphs. We find ${\ensuremath{\rho}}_{c}$ will decrease gradually with growing $C$, and it converges to ${\ensuremath{\rho}}_{\ensuremath{\infty}}$ as $C\ensuremath{\rightarrow}\ensuremath{\infty}$. The CD problem is called the dismantling problem when $C$ is a small finite fraction of $|\mathcal{V}|$. Therefore, ${\ensuremath{\rho}}_{\ensuremath{\infty}}$ is also the lower bound of the dismantling problem when $|\mathcal{V}|\ensuremath{\rightarrow}\ensuremath{\infty}$. To reduce the computation complexity of the BP equations, taking the knowledge of the probability of a random selected vertex belonging to a remaining connected component with the size $A$, the original BP equations can be simplified to one with only three states when $C\ensuremath{\rightarrow}\ensuremath{\infty}$. The simplified BP equations are very similar to the BP equations of the feedback vertex set spin-glass model [H.-J. Zhou, Eur. Phys. J. B 86, 455 (2013)]. Finally, we develop two practical belief-propagation-guide decimation algorithms based on the original BP equations (CD-BPD) and the simplified BP equations (SCD-BPD) to solve the CD problem on a certain graph. Our BPD algorithms and two other state-of-art heuristic algorithms are applied on various random graphs and some real-world networks. Computation results show that the CD-BPD is the best of all tested algorithms in the case of small $C$. But considering the performance and computation consumption, we recommend using SCD-BPD for the network with a small clustering coefficient when $C$ is large.