Fully Dynamic (Δ + 1)-Coloring Against Adaptive Adversaries

Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include (∆ + 1) vertex coloring, maximal independent set, and maximal matching. For all three problems, there are randomized algorithms that maintain a valid solution after each edge insertion or deletion to the n-vertex graph by spending polylog n time, provided that the adversary is oblivious. However, none of these algorithms work against adaptive adversaries whose updates may depend on the output of the algorithm. In fact, even breaking the trivial bound of O(n) against adaptive adversaries remains open for all three problems. For instance, in the case of (∆ + 1) vertex coloring, the main challenge is that an adaptive adversary can keep inserting edges between vertices of the same color, necessitating a recoloring of one of the endpoints. The trivial algorithm would simply scan all neighbors of one endpoint to find a new available color (which always exists) in O(n) time.

In this paper, we break this linear barrier for the (∆ + 1) vertex coloring problem. Our algorithm is randomized, and maintains a valid (∆ + 1) vertex coloring after each edge update by spending O(n 8/9 ) time with high probability.

To achieve this result, we build on a powerful sparse-dense decomposition of graphs developed in previous work. While such a decomposition has been applied to several sublinear models, this is its first application in the dynamic setting. A major challenge in applying this framework to our setting is that it relies on maintaining a perfect matching of a certain graph. While maintaining a perfect matching (conditionally) requires n 1-o(1) time per update, we prove several structural properties of this graph (of possible independent interest) to achieve an update-time that is sublinear in n.