In network vulnerability analysis, evaluating the robustness of $k$-cores against vertex removals is crucial. A $k$-core is often fragile, as removing a few vertices can trigger a significant reduction in core size, a phenomenon known as core collapse.
This paper studies the problem of enumerating all minimal removable sets (MinRSs) of a given $k$-core, where a MinRS is a minimal nonempty set of vertices whose removal results in a smaller $k$-core graph. We consider this problem within a general mathematical framework based on monotone systems.
We demonstrate that for a monotone system given with an underlying graph $G=(V,E)$, all MinRSs of a solution can be enumerated in $O((n+m)n\tau_\omega)$ time, where $n=|V|$, $m=|E|$, and $\tau_\omega$ denotes the computation time of evaluating the monotone function of the system. Furthermore, if the system satisfies the newly defined in-dominating seed property, the complexity drops to $O((n+m) \log n \cdot \tau_\omega)$ time.
We prove that standard $k$-cores in undirected graphs satisfy this property, enabling MinRS enumeration in $O((n+m)\log n)$ time, a significant improvement over the baseline. We also extend our framework to enumerate all solutions in a given monotone system, yielding an $O((n+m)\log n)$-delay algorithm for all $k$-core subgraphs, outperforming an algorithm given by [Boley et al., Theoretical Computer Science, 2010].
Our framework is applicable to various $k$-core extensions, including weighted $k$-cores, multi-layer $\boldsymbol{k}$-cores, and $(k,\ell)$-cores.
Blogger's Review: The efficient algorithm presented in this paper provides a fresh perspective on core collapse analysis, especially in assessing the vulnerabilities of complex networks. By introducing the in-dominating seed property, the algorithm's complexity is significantly reduced, showcasing the broad applicability of monotone systems in graph theory. This holds important theoretical and practical value for studying network stability and optimization problems.