pipette
ESEspañol

Dynamic Vertex Coloring with Adaptive Adversaries: Entropy Compression to the Rescue

Sepehr Assadi, Helia Yazdanyar

Preprint

In the authors' words

We present a randomized algorithm for maintaining a vertex coloring of a fully dynamic graph against an adaptive adversary with amortized update time. Our algorithm improves upon the recent randomized algorithms of Behnezhad, Rajaraman, and Wasim (SODA 2025) with and Flin and Halld\'orsson (ICALP 2025) with amortized update time. Our result (nearly) matches a fundamental limit of update time identified by Flin and Halld\'orsson and settles their main open question. The previous algorithms' main improvement came from efficient coloring of the dense parts of the graph. Our approach complements these prior work by handling the sparse parts more efficiently, using ideas inspired by the recently developed dynamic entropy compression method. A key new aspect of our work is to tailor this method specifically to dynamic algorithms---as opposed to original local search algorithms---and achieve update times that can be sublinear in the number of involved constraints per update.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 57 pages, 6 figures, to appear in SODA 2027