  We study the problem of finding the smallest set of nodes in a network whose
removal results in an empty $k$-core; where the $k$-core is the sub-network
obtained after the iterative removal of all nodes of degree smaller than $k$.
This problem is also known in the literature as finding the minimal contagious
set. The main contribution of our work is an analysis of the performance of the
recently introduced corehd algorithm [Scientific Reports, 6, 37954 (2016)] on
random networks taken from the configuration model via a set of deterministic
differential equations. Our analyses provides upper bounds on the size of the
minimal contagious set that improve over previously known bounds. Our second
contribution is a new heuristic called the weak-neighbor algorithm that
outperforms all currently known local methods in the regimes considered.
