Advice Complexity of Maximum Independent set in Sparse and Bipartite Graphs

摘要

We study the advice complexity of the online version of the Maximum Independent Set problem, restricted to the sparse, and bipartite graphs, respectively. We show that for sparse graphs, constant-sized advice is sufficient to obtain a constant competitive ratio, whereas for bipartite graphs, only competitive ratio Omega(log(n/a)/loglog(n/a)) can be obtained with an advice of size a > loglogn. However, competitive ratio O(logn) can be achieved with advice O(loglogn).