Abstract
The k-core of a graph is its maximal subgraph with minimum degree at least k, and the core value of a vertex u is the largest k for which u is contained in the k-core of the graph. Recently, k-core and its variants have gained significant attention in dynamic graphs, as summarized by Hanauer, Henzinger, and Schulz in their survey on dynamic graph algorithms.
We address questions on k-core stated in the survey, proving that there is no efficient dynamic algorithm for k-core or to find (2 - \epsilon)-approximations for the core values, unless we improve decade-long state-of-the-art algorithms in several areas including matrix multiplication and satisfiability, based on the established OMv and SETH conjectures.
Some of our results demonstrate that no dynamic algorithm for k-core can be asymptotically faster than trivial ones, explaining why recent research papers focus on finding bounded algorithms that perform well when few core values change per update. However, we also prove that such bounded algorithms do not exist based on the OMv conjecture.
Additionally, we present lower bounds for a directed version of the problem and for the edge variant known as k-truss. On a positive note, we present a polylogarithmic dynamic algorithm for 2-core.
Blogger's Review: This paper delves into the computational complexity of k-core in dynamic graphs, highlighting the limitations of current algorithms, particularly in scenarios with frequent dynamic updates. It remains a challenge to design efficient algorithms, while presenting solutions for specific cases, adding significant theoretical and practical value.