License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.25
URN: urn:nbn:de:0030-drops-169637
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16963/
Bosek, Bartłomiej ;
Zych-Pawlewicz, Anna
Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget
Abstract
In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be colored immediately, so that no two overlapping intervals share the same color. After each update only a limited number of intervals are allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper we show, that if the graph remains k-colorable at all times, the updates consist of insertions only, and the final instance consists of n intervals, then we can achieve an amortized recourse budget of ?({k⁷ log n}) while maintaining a proper coloring with k colors. This is an exponential improvement over the result in [Bartłomiej Bosek et al., 2020] in terms of both k and n. We complement this result by showing the lower bound of Ω(n) on the amortized recourse budget in the fully dynamic setting. Our incremental algorithm can be efficiently implemented.
As an additional application of our techniques we include a new combinatorial result on coloring unit circular arc graphs. Let L be the maximum number of arcs intersecting in one point for some set of unit circular arcs ?. We show that if there is a set ?' of non-intersecting unit arcs of size L²-1 such that ? ∪ ?' does not contain L+1 arcs intersecting in one point, then it is possible to color ? with L colors. This complements the work on circular arc coloring [Belkale and Chandran, 2009; Tucker, 1975; Valencia-Pabon, 2003], which specifies sufficient conditions needed to color ? with L+1 colors or more.
BibTeX - Entry
@InProceedings{bosek_et_al:LIPIcs.ESA.2022.25,
author = {Bosek, Bart{\l}omiej and Zych-Pawlewicz, Anna},
title = {{Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {25:1--25:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16963},
URN = {urn:nbn:de:0030-drops-169637},
doi = {10.4230/LIPIcs.ESA.2022.25},
annote = {Keywords: dynamic algorithms, unit interval graphs, coloring, recourse budget, parametrized dynamic algorithms}
}
|
Keywords: |
|
dynamic algorithms, unit interval graphs, coloring, recourse budget, parametrized dynamic algorithms |
|
Collection: |
|
30th Annual European Symposium on Algorithms (ESA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.09.2022 |
