Online graph coloring uses fewer colors with random vertex order
Online Graph Coloring with Random Arrivals
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Graph coloring is a way of assigning colors to points in a network so that connected points have different colors. The paper studies coloring graphs when points appear one by one in a random order. The authors designed a method that uses a relatively small number of colors for certain types of graphs, improving over previous approaches that worked for worst-case orders. Their method allows better performance in an online setting, even though graph coloring is usually very hard to approximate efficiently.
What this means in practice
- •For network schedulers: Assign frequencies or channels in networks dynamically when devices connect in unpredictable order, using fewer resources than worst-case methods.
- •For online resource allocators: Color graphs representing tasks arriving randomly to improve scheduling and allocation with fewer colors than previous online methods.
A theory result. No direct application yet.
Authors
Hirotaka Yoneda, Masataka Yoneda
Abstract
We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming $n$ and $k$ are known in advance, we present a randomized exponential-time algorithm that colors any $k$-colorable graph on $n$ vertices with $O(k^3 \log^2 k \log^4 n)$ colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed $k \geq 3$, and is better than a known lower bound of $Ω(\log^{k-1} n)$ colors under adversarial arrivals for all fixed $k \geq 6$. In addition, assuming $n$ is known in advance, we obtain a competitive ratio of $\widetilde{O}(n^{2/3})$. For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of $n^{1-\varepsilon}$ for all fixed $\varepsilon > 0$. Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.