Dynamic algorithms for k-center on graphs

In this paper we give the first efficient algorithms for the 𝑘-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into 𝑘 sets by choosing 𝑘 centers such that the maximum distance from any data point to its closest center is minimized. It is known that it is NP-hard to get a better than 2 approximation for this problem.

While in many applications the input may naturally be modeled as a graph, all prior works on 𝑘-center problem in dynamic settings are on point sets in arbitrary metric spaces. In this paper, we give a deterministic decremental (2 + 𝜖)-approximation algorithm and a randomized incremental (4 + 𝜖)-approximation algorithm, both with amortized update time 𝑘𝑛 𝑜 (1) for weighted graphs. Moreover, we show a reduction that leads to a fully dynamic (2 +𝜖)approximation algorithm for the 𝑘-center problem, with worst-case update time that is within a factor 𝑘 of the state-of-the-art fully dynamic (1 + 𝜖)-approximation single-source shortest paths algorithm in graphs. Matching this bound is a natural goalpost because the approximate distances of each vertex to its center can be used to maintain a (2 + 𝜖)-approximation of the graph diameter and the fastest known algorithms for such a diameter approximation also rely on maintaining approximate single-source distances.