Bosek, Bartłomiej ;
Disser, Yann ;
Feldmann, Andreas Emil ;
Pawlewicz, Jakub ;
ZychPawlewicz, Anna
Recoloring Interval Graphs with Limited Recourse Budget
Abstract
We consider the problem of coloring an interval graph dynamically. Intervals arrive one after the other and have to be colored immediately such that no two intervals of the same color overlap. In each step only a limited number of intervals may be recolored to maintain a proper coloring (thus interpolating between the wellstudied online and offline settings). The number of allowed recolorings per step is the socalled recourse budget. Our main aim is to prove both upper and lower bounds on the required recourse budget for interval graphs, given a bound on the allowed number of colors.
For general interval graphs with n vertices and chromatic number k it is known that some recoloring is needed even if we have 2k colors available. We give an algorithm that maintains a 2kcoloring with an amortized recourse budget of 𝒪(log n). For maintaining a kcoloring with k ≤ n, we give an amortized upper bound of 𝒪(k⋅ k! ⋅ √n), and a lower bound of Ω(k) for k ∈ 𝒪(√n), which can be as large as Ω(√n).
For unit interval graphs it is known that some recoloring is needed even if we have k+1 colors available. We give an algorithm that maintains a (k+1)coloring with at most 𝒪(k²) recolorings per step in the worst case. We also give a lower bound of Ω(log n) on the amortized recourse budget needed to maintain a kcoloring.
Additionally, for general interval graphs we show that if one does not insist on maintaining an explicit coloring, one can have a kcoloring algorithm which does not incur a factor of 𝒪(k ⋅ k! ⋅ √n) in the running time. For this we provide a data structure, which allows for adding intervals in 𝒪(k² log³ n) amortized time per update and querying for the color of a particular interval in 𝒪(log n) time. Between any two updates, the data structure answers consistently with some optimal coloring. The data structure maintains the coloring implicitly, so the notion of recourse budget does not apply to it.
BibTeX  Entry
@InProceedings{bosek_et_al:LIPIcs:2020:12264,
author = {Bartłomiej Bosek and Yann Disser and Andreas Emil Feldmann and Jakub Pawlewicz and Anna ZychPawlewicz},
title = {{Recoloring Interval Graphs with Limited Recourse Budget}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {17:117:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771504},
ISSN = {18688969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12264},
URN = {urn:nbn:de:0030drops122649},
doi = {10.4230/LIPIcs.SWAT.2020.17},
annote = {Keywords: Colouring, Dynamic Algorithms, Recourse Budget, Interval Graphs}
}
12.06.2020
Keywords: 

Colouring, Dynamic Algorithms, Recourse Budget, Interval Graphs 
Seminar: 

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Issue date: 

2020 
Date of publication: 

12.06.2020 