Tight Bounds for Online Coloring of Basic Graph Classes
- PDF / 1,899,988 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 200 Views
Tight Bounds for Online Coloring of Basic Graph Classes Susanne Albers1 · Sebastian Schraink1 Received: 8 January 2020 / Accepted: 7 August 2020 © The Author(s) 2020
Abstract We resolve a number of long-standing open problems in online graph coloring. More specifically, we develop tight lower bounds on the performance of online algorithms for fundamental graph classes. An important contribution is that our bounds also hold for randomized online algorithms, for which hardly any results were known. Technically, we construct lower bounds for chordal graphs. The constructions then allow us to derive results on the performance of randomized online algorithms for the following further graph classes: trees, planar, bipartite, inductive, bounded-treewidth and disk graphs. It shows that the best competitive ratio of both deterministic and randomized online algorithms is Θ(log n) , where n is the number of vertices of a graph. Furthermore, we prove that this guarantee cannot be improved if an online algorithm has a lookahead of size O(n∕ log n) or access to a reordering buffer of size n1−𝜖 , for any 0 < 𝜖 ≤ 1 . A consequence of our results is that, for all of the above mentioned graph classes except bipartite graphs, the natural First Fit coloring algorithm achieves an optimal performance, up to constant factors, among deterministic and randomized online algorithms. Keywords Graph coloring · Online algorithms · Lower bounds · Randomization
1 Introduction Online graph coloring is a classical problem in graph theory and online computation. It has applications in job scheduling, dynamic storage allocation and resource management in wireless networks [24, 28, 29]. A problem instance is defined by A preliminary version of the paper has appeared in the 25th Annual European Symposium on Algorithms (ESA’17). Work supported by the European Research Council, Grant Agreement No. 691672, project APEG. * Susanne Albers [email protected] Sebastian Schraink [email protected] 1
Department of Computer Science, Technical University of Munich, Garching, Germany
13
Vol.:(0123456789)
Algorithmica
an undirected graph G = (V, E) , consisting of a vertex set V and an edge set E. Let |V| = n . The vertices arrive one by one in a sequence 𝜎 = v1 , … , vn that may be determined by an adversary. Whenever a new vertex vt arrives, 1 ≤ t ≤ n , its edges to previous vertices vs with s < t are revealed. An online algorithm A has to immediately assign a feasible color to vt , i.e. a color that is different from those assigned to the neighbors of vt presented so far. The goal is to minimize the total number of colors used. For a graph G, let A(G) be the number of colors used by A . Let 𝜒(G) be the chromatic number of G, which is the minimum number of colors needed to color G offline. An online algorithm A is c-competitive if there exists a constant b such that A(G) ≤ c ⋅ 𝜒(G) + b holds for every graph G [30]. The additive constant b must be independent of the input graph G. If A is a randomized algorithm, then E[A(G)] is the expected number of col
Data Loading...
