  C-dismantling (CD) problem aims at finding the minimum vertex set D of a
graph G(V,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 by the belief-propagation (BP)
equations under the replica-symmetry ansatz. We give the lower bound $\rho_c$
of the relative size of D with finite C on regular random graphs and
Erdos-Renyi random graphs. We find $\rho_c$ will decrease gradually with
growing C and it converges to $\rho_\infty$ as C$\to\infty$. The CD problem is
called dismantling problem when C is a small finite fraction of |V|. Therefore,
$\rho_\infty$ is also the lower bound of the dismantling problem when
|V|$\to\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$\to\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)]. At
last, 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 in 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 small clustering coefficient when C is large.
