Online independent sets

We study the online version of the independent set problem in graphs. The vertices of an input graph are given one by one along with their edges to previous vertices, and the task is to decide whether to add each given vertex to an independent set solution. The goal is to maximize the size of the independent set, relative to the size of the optimal independent set. Since it is known that no online algorithm can attain competitive ratio better than n - 1, where n denotes the number of vertices, we study here relaxations where the algorithm can hedge its bets by maintaining multiple alternative solutions. We introduce two models. In the first model, the algorithm can maintain a multiple number (r(n)) of solutions (independent sets) and choose the largest one as the final solution. We show that the best competitive ratio for this model is theta(n/log n) when r(n) is a polynomial and theta(n) when r(n) is a constant. In the second more powerful model, the algorithm can copy intermediate solutions and extend the copied solutions in different ways. We obtain an upper bound O(n/log n) and a lower bound Omega(n/log(3)n) for the best possible competitive ratio when r(n) is a polynomial. Furthermore, we show a tight theta(n) bound when r(n) is a constant. Lower bound results of this paper hold also for randomized online algorithms against an oblivious adversary. (C) 2002 Elsevier Science B.V. All rights reserved.