2026-09-08T02:21:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26459 2026-09-05T19:44:15Z ddc:004 open_access

Incremental (k, z)-Clustering on Graphs Cruciani, Emilio Forster, Sebastian Skarlatos, Antonis (k z)-clustering k-median k-means dynamic graph algorithms 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. This problem includes the well-known k-median (z = 1) and k-means (z = 2) clustering problems. 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. Prior works by Bhattacharya, Costa, Garg, Lattanzi, and Parotsidis [FOCS 2024] and by Bhattacharya, Costa, and Farokhnejad [STOC 2025] consider the dynamic (k, z)-clustering problem for point sets in metric spaces. These algorithms support adversarial point insertions and deletions under a model with access to pairwise distances. This model differs significantly from the dynamic graph setting, where no oracle access is given to pairwise distances and a single edge update can affect many distances - making these approaches inefficient when applied to graphs. While efficient dynamic k-center approximation algorithms on graphs exist [Cruciani, Forster, Goranci, Nazari, and Skarlatos, 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 Õ(k m^{1+o(1)} + k^{1+1/(λ)} m), where λ ≥ 1 is an arbitrary fixed constant. Our incremental algorithm also achieves an amortized update time of Õ(k n^o(1) + k^{1+1/(λ)}) and consists of two stages. In the first stage, we maintain a constant-factor bicriteria approximate solution of size Õ(k) with a total update time of m^{1+o(1)} (independent of the parameter k) over all adversarial edge insertions. This first stage is an intricate adaptation of the bicriteria approximation algorithm by Mettu and Plaxton [Machine Learning 2004] to incremental graphs. One of our key technical results is that the radii in their algorithm can be assumed to be non-decreasing while the approximation ratio remains constant - a property that may be of independent interest. In the second stage, we maintain a constant-factor approximate (k,z)-clustering solution on a dynamic weighted instance induced by the bicriteria approximate solution. For this subproblem, we employ a dynamic spanner algorithm together with a static (k,z)-clustering algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emilio Cruciani and Sebastian Forster and Antonis Skarlatos 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.70 urn:nbn:de:0030-drops-264599 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.70 eng https://creativecommons.org/licenses/by/4.0/legalcode