Tree coloring with predictions

Discrete Applied Mathematics, vol. 380, pp. 386–394

Abstract

Graph coloring is a notoriously challenging problem, especially when considering the online setting where each arriving vertex must be colored immediately and irreversibly. Even on trees, which are trivially two-colorable, achieving anything better than a logarithmic competitive ratio becomes impossible if the order of arrival is adversarially determined. We investigate tree coloring in a slightly relaxed model where vertices arrive online but in random order, focusing specifically on algorithms with predictions of varying reliability. Furthermore, we extend our analysis to all two-colorable graphs and provide matching lower bounds for both cases.

Authors 7

1. Fabian Frei

   Helmholtz Center for Information Security

   Affiliation as printed

   CISPA Helmholtz Center for Information Security, Germany

2. Matthias Gehnen Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Germany

3. Dennis Komm

   ETH Zurich

   Affiliation as printed

   Department of Computer Science, ETH Zurich, Switzerland

4. Rastislav Kráľovič

   ETH Zurich

   Affiliation as printed

   Department of Computer Science, ETH Zurich, Switzerland

5. Richard Královič

   ETH Zurich

   Affiliation as printed

   Department of Computer Science, ETH Zurich, Switzerland

6. Peter Rossmanith Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Germany

7. Moritz Stocker corresponding

   ETH Zurich

   Affiliation as printed

   Department of Computer Science, ETH Zurich, Switzerland