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
Go to the corresponding LIPIcs Volume Portal

Bosek, Bartłomiej ; Zych-Pawlewicz, Anna

Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget

LIPIcs-ESA-2022-25.pdf (0.8 MB)


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

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI