License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.59
URN: urn:nbn:de:0030-drops-64713
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6471/
Komm, Dennis ;
Královic, Rastislav ;
Královic, Richard ;
Kudahl, Christian
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.
BibTeX - Entry
@InProceedings{komm_et_al:LIPIcs:2016:6471,
author = {Dennis Komm and Rastislav Kr{\'a}lovic and Richard Kr{\'a}lovic and Christian Kudahl},
title = {{Advice Complexity of the Online Induced Subgraph Problem}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {59:1--59:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6471},
URN = {urn:nbn:de:0030-drops-64713},
doi = {10.4230/LIPIcs.MFCS.2016.59},
annote = {Keywords: online algorithms, advice complexity, induced subgraph problem}
}
|
Keywords: |
|
online algorithms, advice complexity, induced subgraph problem |
|
Collection: |
|
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.08.2016 |
