Advice Complexity of the Online Induced Subgraph Problem

Dennis Komm, Rastislav Královič, Richard Královič, Christian Kudahl

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

50 Downloads (Pure)

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 languageEnglish
Title of host publicationProceeding of the 41st International Symposium on Mathematical Foundations of Computer Science
EditorsPiotr Faliszewski, Anca Muscholl, Rolf Niedermeier
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Publication date22. Aug 2016
Pages1-13
Article number59
ISBN (Electronic)978-3-95977-016-3
DOIs
Publication statusPublished - 22. Aug 2016
Event41st International Symposium on Mathematical Foundations of Computer Science - AGH University, Krakow, Poland
Duration: 22. Aug 201626. Aug 2016
http://mfcs.ki.agh.edu.pl/

Conference

Conference41st International Symposium on Mathematical Foundations of Computer Science
LocationAGH University
CountryPoland
CityKrakow
Period22/08/201626/08/2016
Internet address
SeriesLeibniz International Proceedings in Informatics
Volume58
ISSN1868-8969

Keywords

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

Fingerprint Dive into the research topics of 'Advice Complexity of the Online Induced Subgraph Problem'. Together they form a unique fingerprint.

Cite this