Advice complexity of the online induced subgraph problem

DOI10.4230/LIPICS.MFCS.2016.59zbMATH Open1398.68691arXiv1512.05996OpenAlexW2962942578MaRDI QIDQ4608622FDOQ4608622

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

Publication date: 21 March 2018

Abstract: Several well-studied graph problems aim to select a largest (or smallest) induced subgraph with a given property of the input graph. Examples of such problems include maximum independent set, maximum planar graph, and many others. We consider these problems, where the vertices are presented online. With each vertex, the online algorithm must 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 the generalized problem: for a hereditary property pty, find some maximal induced subgraph having pty. We study this problem from the point of view of advice complexity. Using a result from Boyar et al. [STACS 2015], 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 pty, for any c (possibly a function of n). Surprisingly, a similar result cannot be obtained for the symmetric problem: for a given cohereditary property pty, find a minimum subgraph having pty. We show that the advice complexity of this problem varies significantly with the choice of pty. We also consider preemptive online model, 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 again. We show that, for the maximum induced subgraph problem, preemption cannot help much, giving a lower bound of $Omega(n/(c^{2}logc))$ bits of advice needed to obtain competitive ratio $c$, where $c$ is any increasing function bounded by sqrt{n/log n}. We also give a linear lower bound for c close to 1.

Full work available at URL: https://arxiv.org/abs/1512.05996

Recommendations

• Advice complexity for a class of online problems
• The advice complexity of a class of hard online problems
• Independent set with advice: the impact of graph knowledge (extended abstract)
• On the Advice Complexity of Online Edge- and Node-Deletion Problems
• scientific article; zbMATH DE number 2079869

zbMATH Keywords

online algorithmsadvice complexityinduced subgraph problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75)

Cited In (13)

• On the advice complexity of the online dominating set problem
• Reducing off-line to on-line: An example and its applications
• Weighted online problems with advice
• Independent set with advice: the impact of graph knowledge (extended abstract)
• Advice complexity of adaptive priority algorithms
• On-line computation and maximum-weighted hereditary subgraph problems
• Advice complexity of online non-crossing matching
• On the Advice Complexity of Online Edge- and Node-Deletion Problems
• On the Advice Complexity of Online Problems
• On-line maximum-order induced hereditary subgraph problems
• Title not available (Why is that?)
• Further results on online node- and edge-deletion problems with advice
• Online node- and edge-deletion problems with advice

This page was built for publication: Advice complexity of the online induced subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608622)