Solomon, Shay ;
Wein, Nicole
Improved Dynamic Graph Coloring
Abstract
This paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within n^{1epsilon} for any epsilon > 0, is NPhard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting. It is therefore only natural to consider the combinatorial aspects of dynamic coloring, or alternatively, study restricted families of graphs.
Towards understanding the combinatorial aspects of this problem, one may assume a blackbox access to a static algorithm for Ccoloring any subgraph of the dynamic graph, and investigate the tradeoff between the number of colors and the number of recolorings per update step. Optimizing the number of recolorings, sometimes referred to as the recourse bound, is important for various practical applications. In WADS'17, Barba et al. devised two complementary algorithms: For any beta > 0, the first (respectively, second) maintains an O(C beta n^{1/beta}) (resp., O(C beta))coloring while recoloring O(beta) (resp., O(beta n^{1/beta})) vertices per update. Barba et al. also showed that the second tradeoff appears to exhibit the right behavior, at least for beta = O(1): Any algorithm that maintains a ccoloring of an nvertex dynamic forest must recolor Omega(n^{2/(c(c1))}) vertices per update, for any constant c >= 2. Our contribution is twofold:
 We devise a new algorithm for general graphs that improves significantly upon the first tradeoff in a wide range of parameters: For any beta > 0, we get a O~(C/(beta)log^2 n)coloring with O(beta) recolorings per update, where the O~ notation supresses polyloglog(n) factors. In particular, for beta = O(1) we get constant recolorings with polylog(n) colors; not only is this an exponential improvement over the previous bound, but it also unveils a rather surprising phenomenon: The tradeoff between the number of colors and recolorings is highly nonsymmetric.
 For uniformly sparse graphs, we use low outdegree orientations to strengthen the above result by bounding the update time of the algorithm rather than the number of recolorings. Then, we further improve this result by introducing a new data structure that refines bounded outdegree edge orientations and is of independent interest.
BibTeX  Entry
@InProceedings{solomon_et_al:LIPIcs:2018:9535,
author = {Shay Solomon and Nicole Wein},
title = {{Improved Dynamic Graph Coloring}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {72:172:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9535},
URN = {urn:nbn:de:0030drops95357},
doi = {10.4230/LIPIcs.ESA.2018.72},
annote = {Keywords: coloring, dynamic graph algorithms, graph arboricity, edge orientations}
}
2018
Keywords: 

coloring, dynamic graph algorithms, graph arboricity, edge orientations 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 