## 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 π, find some maximal induced subgraph having π. 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 π, 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 (n
^{1-log}
_{4}
^{3-o} (1)). Surprisingly, for a given cohereditary property π and the objective to find a minimum subgraph having π, the advice complexity varies significantly with the choice of π. 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 (n/(c
^{2} log c)) on the bits of advice that are needed to obtain competitive ratio c, where c is any increasing function bounded from above by √ n/ log n. We also give a linear lower bound for c close to 1.

Original language | English |
---|---|

Title of host publication | Proceeding of the 41st International Symposium on Mathematical Foundations of Computer Science |

Editors | Piotr Faliszewski, Anca Muscholl, Rolf Niedermeier |

Publisher | Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik |

Publication date | 22. Aug 2016 |

Pages | 1-13 |

Article number | 59 |

ISBN (Electronic) | 978-3-95977-016-3 |

DOIs | |

Publication status | Published - 22. Aug 2016 |

Event | 41st International Symposium on Mathematical Foundations of Computer Science - AGH University, Krakow, Poland Duration: 22. Aug 2016 → 26. Aug 2016 http://mfcs.ki.agh.edu.pl/ |

### Conference

Conference | 41st International Symposium on Mathematical Foundations of Computer Science |
---|---|

Location | AGH University |

Country | Poland |

City | Krakow |

Period | 22/08/2016 → 26/08/2016 |

Internet address |

Series | Leibniz International Proceedings in Informatics |
---|---|

Volume | 58 |

ISSN | 1868-8969 |

## Keywords

- online algorithms
- induced subgraph
- advice complexity
- Online algorithms
- Advice complexity
- Induced subgraph problem