在网络脆弱性分析中，评估 $k$-核心对顶点移除的鲁棒性至关重要。$k$-核心通常脆弱，因为移除少量顶点可能会导致核心规模的大幅减少，这种现象被称为核心崩溃。
本文研究了枚举给定 $k$-核心的所有最小可移除集合（MinRSs）的问题，其中 MinRS 是一个最小的非空顶点集合，其移除会导致更小的 $k$-核心图。我们在基于单调系统的一般数学框架内考虑此问题。
我们证明，对于给定底层图 $G=(V,E)$ 的单调系统，所有 MinRS 的枚举可以在 $O((n+m)n\tau_\omega)$ 时间内完成，其中 $n=|V|$，$m=|E|$，而 $\tau_\omega$ 表示评估系统单调函数的计算时间。此外，如果系统满足新定义的入主种子属性，则复杂度降至 $O((n+m) \log n \cdot \tau_\omega)$ 时间。
我们证明标准的 $k$-核心在无向图中满足此属性，从而使得 MinRS 的枚举时间为 $O((n+m)\log n)$，这是对基线的显著改进。我们还扩展了我们的框架，以枚举给定单调系统中的所有解。这为所有 $k$-核心子图提供了一个 $O((n+m)\log n)$ 的延迟算法，优于 [Boley et al., Theoretical Computer Science, 2010] 提供的算法。
我们的框架适用于各种 $k$-核心扩展，包括加权 $k$-核心、多层 $\boldsymbol{k}$-核心和 $(k,\ell)$-核心。
博主点评： 本文提出的高效算法在核心崩溃分析中提供了新的思路，尤其是在处理复杂网络的脆弱性评估时。通过引入入主种子属性，显著降低了算法复杂度，展现了单调系统在图论中的广泛应用潜力。对于研究网络结构稳定性和优化问题具有重要的理论与实用价值。