Advice Complexity of the Online Induced Subgraph Problem

Abstract

Several well-studied graph problems aim to select a largest (or smallest) induced subgraph with a given property of the input graph.  Examples include maximum independent set, maximum planar graph, maximum clique, minimum feedback vertex set, and many others.  In online versions of these problems, the vertices of the graph are presented in an adversarial order, and with each vertex, the online algorithm must irreversibly decide whether to include it into the constructed subgraph, based only on the subgraph induced by the vertices presented so far.  We study the properties that are common to all these problems by investigating a generalized problem: for an arbitrary but fixed hereditary property pi, find some maximal induced subgraph having pi. We investigate this problem from the point of view of advice complexity, i.e., we ask how some additional information about the yet unrevealed parts of the input can influence the solution quality.  We evaluate the information in a quantitative way by considering the best possible advice of given size that describes the unknown input.  Using a result from Boyar et al. [STACS 2015, LIPIcs 30], we give a tight trade-off relationship stating that, for inputs of length n, roughly n/c bits of advice are both needed and  sufficient to obtain a solution with competitive ratio c, regardless of the choice of pi, for any c (possibly a function of n).  This complements the results from Bartal et al. [SIAM Journal on Computing 36(2), 2006] stating that, without any advice, even a randomized  algorithm cannot achieve a competitive ratio better than Omega(n^{1-log_{4}3-o(1)}).  Surprisingly, for a given cohereditary property pi and the objective to find a minimum subgraph having pi, the advice complexity varies significantly with the choice of pi. We also consider a preemptive online model, inspired by some applications mainly in networking and scheduling, where the decision of the  algorithm is not completely irreversible.  In particular, the algorithm may discard some vertices previously assigned to the constructed set, but discarded vertices cannot be reinserted into the set.  We show that, for the maximum induced subgraph problem,  preemption does not significantly help by giving a lower bound of Omega(n/(c^2log c)) on the bits of advice that are needed to obtain
  competitive ratio c, where c is any increasing function bounded from above by sqrt(n/log n).  We also give a linear lower bound for c close to 1.