[2602.08542] Incremental (k, z)-Clustering on Graphs

Computer Science > Data Structures and Algorithms arXiv:2602.08542 (cs) [Submitted on 9 Feb 2026 (v1), last revised 1 Mar 2026 (this version, v2)] Title:Incremental (k, z)-Clustering on Graphs Authors:Emilio Cruciani, Sebastian Forster, Antonis Skarlatos View a PDF of the paper titled Incremental (k, z)-Clustering on Graphs, by Emilio Cruciani and 2 other authors View PDF Abstract:Given a weighted undirected graph, a number of clusters $k$, and an exponent $z$, the goal in the $(k, z)$-clustering problem on graphs is to select $k$ vertices as centers that minimize the sum of the distances raised to the power $z$ of each vertex to its closest center. In the dynamic setting, the graph is subject to adversarial edge updates, and the goal is to maintain explicitly an exact $(k, z)$-clustering solution in the induced shortest-path metric. While efficient dynamic $k$-center approximation algorithms on graphs exist [Cruciani et al. SODA 2024], to the best of our knowledge, no prior work provides similar results for the dynamic $(k,z)$-clustering problem. As the main result of this paper, we develop a randomized incremental $(k, z)$-clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of $\tilde O(k m^{1+o(1)}+ k^{1+\frac{1}{\lambda}} m)$, where $\lambda \geq 1$ is an arbitrary fixed constant. Our incremental algorithm consists of two stages. In the first stage, we maintain a consta...