Faster Dynamic ( Δ + 1 ) (\Delta+1) -Coloring Against Adaptive Adversaries
Maxime Flin, Magnús M. Halldórsson · 2025
Read Faster Dynamic ( Δ + 1 ) (\Delta+1) -Coloring Against Adaptive Adversaries by Maxime Flin, Magnús M. Halldórsson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19729.txt.
Introduction
Maxime Flin and Magnús Halldórsson speed up the task of keeping a changing network properly colored. Their work appeared in twenty twenty-five. In graph coloring, linked nodes must differ in color, and edges here appear and vanish over time.
Their randomized algorithm maintains a coloring with one more color than the highest node degree. It runs against an adaptive adversary, meaning each change can react to the algorithm's past choices. The update time beats a very recent rival result and reaches a natural barrier for this problem. The gains come from the densest parts of the graph. The authors borrow structural ideas from distributed computing, where many machines color a graph together.
Catalog record
| CREATOR | Maxime Flin, Magnús M. Halldórsson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19729
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Faster Dynamic ( Δ + 1 ) (\Delta+1) -Coloring Against Adaptive Adversaries Thanks: This work was supported by the Icelandic Research Fund grants 217965 and 2310015. Maxime Flin, Magnús M. Halldórsson Abstract . We consider the problem of maintaining a proper ( Δ + 1 ) (\Delta+1) -vertex coloring in a graph on n n -vertices and maximum degree Δ \Delta undergoing edge insertions and deletions. We give a randomized algorithm with amortized update time O ~ ( n 2 / 3 ) \widetilde{O}(n^{2/3}) against adaptive adversaries, meaning that updates may depend on past decisions by the algorithm. This improves on the very recent O ~ ( n 8 / 9 ) \widetilde{O}(n^{8/9}) -update-time algorithm by Behnezhad, Rajaraman, and Wasim (SODA 2025) and matches a natural barrier for dynamic ( Δ + 1 ) (\Delta+1) -coloring algorithms. The main improvements are in the densest regions of the graph, where we use structural hints from the study of distributed graph algorithms. 1. Introduction In the (\Delta+1) -coloring problem, we are given a graph with maximum degree \Delta and must assign to each vertex v a color \varphi(v)\in\{1,2,\ldots,\Delta+1\} such that adjacent vertices receive different colors. Despite its simplicity in the classical RAM model, this problem is surprisingly challenging in more constrained models such as distributed graphs [ Lin92 , BEPS16 , HSS18 , CLP20 ] , sublinear models [ ACK19 , CFG+19 , CDP21 , AY25 ] , dynamic graphs [ BCHN18 , HP22 , BGK+22 , BRW25 ] and even recently communication complexity [ FM24 , CMNS24 ] . This paper presents a fully dynamic algorithm for the (\Delta+1) -coloring problem. The vertex set is fixed of size n , while edges can be inserted or deleted as long as the maximum degree remains at most \Delta at all times. We assume \Delta is known in advance. As the graph changes, our algorithm must maintain a (\Delta+1) -coloring. The time the algorithm takes to process an edge insertion or deletion is called the update time and our aim is to minimize it. The study of dynamic algorithms for (\Delta+1) -coloring was initiated by [ BCHN18 ] , which provided a randomized algorithm with O(\log n) amortized update time. Independently, the authors of [ BGK+22 ] and [ HP22 ] provided randomized algorithms with O(1) amortized update time. The caveat with those algorithms is that they assume updates are oblivious : all edge insertions and deletions are fixed in advance and may not adapt to the colors chosen by the algorithm. Maintaining a coloring against an adaptive adversary — that may base the updates on past decisions by the algorithm — is significantly harder, as the adversary can force the algorithm to recolor vertices at every update by connecting same-colored vertices. Until very recently, no o(n) update time algorithm was known for (\Delta+1) -coloring against adaptive adversaries. In a recent breakthrough, Behnezhad, Rajaraman, and Wasim [ BRW25 ] presented a randomized algorithm with \widetilde{O}(n^{8/9}) amortized update time against adaptive adversaries 1 1 1 In this paper, we use \widetilde{O}(f(n)):=O(f(n)\cdot\mbox{\rm poly}(\log n)) to hide polylogarithmic factors. . In this paper, we significantly improve the runtime, obtaining the following result. Theorem 1 . There exists a randomized fully dynamic algorithm maintaining a (\Delta+1) -coloring against adaptive adversaries in \widetilde{O}(n^{2/3}) amortized update time with high probability. At its core, our algorithm is based on a structural decomposition of the vertices into four layers so that vertices of the bottom layer can be colored efficiently by maintaining and searching small sets. Vertices of higher layers are colored by random color trials enhanced with a color stealing mechanism. Specifically, when a vertex cannot use a color due to a lower-level neighbor, our algorithm steals the color and recolors the lower-level vertex instead. Interestingly, the layers correspond to the order in which streaming and distributed algorithms build their colorings. In addition to the runtime improvement, our algorithm approaches a natural barrier for dynamic coloring algorithms against adaptive adversaries. The algorithm of [ BRW25 ] was primarily limited by the challenge of efficiently recoloring dense regions of the graph. In contrast, our algorithm shifts this bottleneck to the recoloring of sparser vertices and the handling of random color trials in general. We elaborate on this in the following discussion. 1.1. Discussion & Open Problems Before we explain why n^{2/3} is a natural barrier, we first establish why n^{1/2} poses a fundamental limit for dynamic algorithms based on random color trials. Observe that this limitation extends to simpler problems, such as 2\Delta -coloring. The bottleneck for recoloring a vertex lies in efficiently verifying whether a color is available. One possibility is to iterate through all neighbors in O(\Delta) time; another is to iterate through color classes (i.e., the set of vertices with a given color). At best, all color classes contain O(n/\Delta) vertices each. So, any algorithm that checks arbitrary or random colors using the former method when \Delta is small and the latter when \Delta is large therefore has O(n^{1/2}) update time at best. Recall that an adaptive adversary can trigger recoloring at every update, preventing any opportunity for amortization. To reduce the number of colors to \Delta+1 , the approach of [ EPS15 , HSS18 , ACK19 , CLP20 , BRW25 ] and ours is to compute a partial coloring in which (sparse) vertices have many pairs of neighbors colored the same. The randomized argument underlying this approach is fragile, requiring a complete rerun every \Theta(\Delta) update. Since it is based on random color trials at every vertex, it runs in O(n^{2}/\Delta) time. Amortized and balanced with the O(\Delta) update time for small \Delta , we obtain the n^{2/3} update time. Problem 1 . Does there exist a fully dynamic (\Delta+1) -coloring with o(n^{2/3}) update time that remains robust against adaptive adversaries? 1.2. Organization of the Paper In Section 2 , we provide a high-level overview of our algorithm and compare it with [ BRW25 ] . Section 3 introduces the sparser-denser decomposition that forms the foundation of our approach. The core of our dynamic algorithm, along with the proof of Theorem 1 , is presented in Section 4 . Finally, we defer the least novel part of our algorithm – the periodic recomputation of a fresh coloring of the whole graph – to Section 5 . 2. Overview We present the key concepts underlying Theorem 1 , deliberately simplifying certain technical details for the sake of intuition. We focus on the case where \Delta\geqslant n^{2/3} , as an update time of O(\Delta) is straightforward to achieve by examining the adjacency list of the vertices. The Sparser-Denser Decomposition. We employ a modified version of the structural decomposition introduced by Reed [ Ree98 ] , and further explored in [ HSS18 , ACK19 ] , which partitions the vertices into sparse vertices and dense clusters. We classify vertices into clusters based on their average density. Vertices in clusters with low average density are designated as sparser , while those in clusters with higher average density are considered denser (see Definition 3.3 ). This method is based on structural observations about the mean local density within a cluster (see Lemma 3.6 ), and provides a significant efficiency gain