Problem 97: Local Computation Algorithm for MIS

From Open Problems in Sublinear Algorithms
Revision as of 18:16, 26 August 2019 by Krzysztof Onak (talk | contribs) (Krzysztof Onak moved page Waiting:Local Computation Algorithm for MIS to Open Problems:97 without leaving a redirect)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Suggested by Mohsen Gaffhari
Source WOLA 2019
Short link https://sublinear.info/97

In the model of Local Computation Algorithms (LCA), given an input graph $G=(V,E)$, an algorithm gets, upon query any vertex $v$ of its choosing, the list of neighbors of $v$. In this model, the current state-of-the-art for the query complexity of computing a Maximal Independent Set (MIS) for graph $G$ of maximum degree at most $\Delta$ is an upper bound of $$ \Delta^{O(\log\log \Delta)} \operatorname{poly}\!\log n $$ queries.

Question: Does there exist a $\operatorname{poly}(\log n, \Delta)$-query LCA for MIS?