Seminár z teoretickej informatiky - Rastislav Královič (13.11.2015)

v piatok 13.11.2015 o 11:00 hod. v miestnosti M/213

---

Prednášajúci: Rasťo Královič

Názov prednášky: Advice Complexity of the Online Induced Subgraph Problem

Termín: 13.11.2015, 11:00 hod., M/213

 

Abstrakt:
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, maximum induced clique, maximum acyclic subgraph, and many others. In online versions of these problems, 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 the generalized problem: for an arbitrary but fixed hereditary property π, find some maximal induced subgraph having π. We study 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 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 π. Surprisingly, a similar result cannot be obtained for the symmetric problem: for a given cohereditary property π, find a minimum subgraph having π. We show that the advice complexity of this problem varies significantly with the choice of π. We also consider the so-called preemptive online model where the decision of the algorithm is not completely irreversible.

web:  http://kedrigern.dcs.fmph.uniba.sk/STI2
rss:  http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php

---