Online Coloring and a New Type of Adversary for Online Graph Problems
share
We introduce a new type of adversary for online graph problems. The new adversary is parameterized by a single integer κ, which upper bounds the number of connected components that the adversary can use at any time during the presentation of the online graph G. We call this adversary "κ components bounded", or κ-CB for short. On one hand, this adversary is restricted compared to the classical adversary because of the κ-CB constraint. On the other hand, we seek competitive ratios parameterized only by κ with no dependence on the input length n, thereby giving the new adversary power to use arbitrarily large inputs. We study online coloring under the κ-CB adversary. We obtain finer analysis of the existing algorithms FirstFit and CBIP by computing their competitive ratios on trees and bipartite graphs under the new adversary. Surprisingly, FirstFit outperforms CBIP on trees. When it comes to bipartite graphs FirstFit is no longer competitive under the new adversary, while CBIP uses at most 2κ colors. We also study several well known classes of graphs, such as 3-colorable, C_k-free, d-inductive, planar, and bounded treewidth, with respect to online coloring under the κ-CB adversary. We demonstrate that the extra adversarial power of unbounded input length outweighs the restriction on the number of connected components leading to non existence of competitive algorithms for these classes.
READ FULL TEXT