Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929681441226752 |
|---|---|
| author | Behnezhad, Soheil Rajaraman, Rajmohan Wasim, Omer |
| author_facet | Behnezhad, Soheil Rajaraman, Rajmohan Wasim, Omer |
| contents | 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 $\widetilde{O}(n^{8/9})$ time with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04418 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries Behnezhad, Soheil Rajaraman, Rajmohan Wasim, Omer Data Structures and Algorithms 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 $\widetilde{O}(n^{8/9})$ time with high probability. |
| title | Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.04418 |