Dynamic Algorithms for k-Center on Graphs
Based on Goranci, Nazaris, Cruciani, Forster, Skarlatos (SODA 2024)
[Bhupendra Dangi]
COSC6385: Analysis of Algorithms
September 20, 2025
1 / 12
Agenda
1 k-Center Problem
2 Dynamic Graph Challenge
3 Solution Overview
4 Decremental Algorithm
5 Incremental Algorithm
6 Fully Dynamic Algorithm
7 Results
8 Applications
9 Open Problems & Future Work
2 / 12
k-Center Problem
Intuition (hospital analogy):
Place k hospitals in a city (nodes = neighborhoods, edges = roads).
Objective: minimize the maximum distance from any node to its nearest hospital (the
radius).
Classic clustering; NP-hard. Best possible approximation factor is 2.
3 / 12
Dynamic Graph Challenge
Real networks change:
Deletions: a bridge closes ⇒ distances increase.
Insertions: a highway opens ⇒ distances shrink.
One change can alter many shortest paths.
Recomputing from scratch after each update is too slow ⇒ need dynamic algorithms.
Road Closed Road Added
4 / 12
Solution Overview: Reduce to MIS
Key Trick: Reduce k-center to Maximal Independent Set (MIS) in a threshold graph.
1 Guess a radius R.
2 Build a threshold graph: connect u, v if dist(u, v) ≤ R.
3 Compute an MIS ⇒ candidate centers.
4 If |centers| ≤ k, success; else R was too small.
5 / 12
Decremental Algorithm (Bridge Closures)
Only edge deletions ⇒ distances increase.
Once centers are well-separated, they stay well-separated.
Maintain structures for decremental shortest paths; adjust clusters with low recourse.
Guarantee: (2 + ε)-approximation (near-optimal).
6 / 12
Incremental Algorithm (Highway Opens)
Only edge insertions ⇒ distances shrink.
Centers can become “too close” ⇒ MIS property may break.
Fix: find a small dominating set S (Õ(k)) and maintain a ruling set/MIS inside S.
Guarantee: (4 + ε)-approximation (weaker but efficient).
7 / 12
Fully Dynamic Algorithm (Both Insertions & Deletions)
Based on Gonzalez’s greedy (farthest-first) algorithm:
1 Pick any center.
2 Repeatedly add the node farthest from current centers, until k centers.
Support with fully dynamic shortest path data structures.
Guarantee: (2 + ε)-approximation.
8 / 12
Results Summary
Case Approximation Update Time
Decremental (deletions) (2 + ε) k · no(1) (amortized)
Incremental (insertions) (4 + ε) k · no(1) (amortized)
Fully Dynamic (both) (2 + ε) O(kn1.823 ) (worst-case)
Decremental & fully dynamic: near the best possible factor (2 + ε).
Incremental is weaker at (4 + ε) due to insertions shrinking distances.
9 / 12
Real-World Applications
10 / 12
Open Problems & Future Work
Can incremental be improved from (4 + ε) to (2 + ε)?
Faster update times (reduce or remove k-dependence).
Parallel / distributed implementations at scale.
Dynamic maintenance of (bounded) MIS/ruling sets more generally.
11 / 12
Thank You!
12 / 12
