摘要
图的 k-core 是其最大子图，且最小度数至少为 k，而顶点 u 的核心值是包含在图 k-core 中的最大 k。近年来，k-core 及其变体在动态图中受到广泛关注，Hanauer、Henzinger 和 Schulz 在其关于动态图算法的调研中对此进行了总结。
我们针对调研中提出的 k-core 问题进行了回答，证明在没有改进包括矩阵乘法和可满足性在内的多个领域的十年领先算法的情况下，无法设计出高效的动态算法来求解 k-core 或寻找 (2 - \epsilon)-近似核心值，这基于已建立的 OMv 和 SETH 猜想。
我们的部分结果显示，k-core 的动态算法不可能比平凡算法更快，这也解释了为什么该领域最近的研究主要集中在寻找一个有界算法上，该算法在核心值每次更新时变化不大时表现良好。然而，我们还证明了基于 OMv 猜想，这类有界算法并不存在。
我们还为问题的有向版本和边变体（称为 k-truss）提供了下界。幸运的是，我们提出了一种针对 2-core 的多对数动态算法。
博主点评： 本文深入探讨了动态图中 k-core 的计算复杂性，揭示了当前算法的局限性，尤其是在动态更新频繁的情况下，如何设计高效算法仍然是一个挑战，同时提出了对特定情况下的解决方案，具有重要的理论和应用价值。