WAOA 2018 Paper Abstract

TITLE: Sublinear graph augmentation for fast query implementation
AUTHORS: Artur Czumaj, Yishay Mansour and Shai Vardi

Abstract:
We introduce the problem of augmenting graphs with sublinear memory in order to speed up replies to queries. As a concrete example, we focus on the following problem: the input is an (unpartitioned) bipartite graph $G=(V,E)$. Given a query $q \in V$, the algorithm's goal is to output $q$'s color in some legal $2$-coloring of $G$, using few probes to the graph. All replies have to be consistent with the same 2-coloring. 
We show that if a linear amount of preprocessing is allowed, there is a randomized algorithm that, for any $\alpha$, uses $O\left( \frac{m}{\alpha}\right) $ probes and $\tilde{O}(\alpha)$ memory, where $m$ is the number of edges in the graph. On the negative side, we show that for a natural family of algorithms that we call probe-first local computation algorithms, this trade-off is optimal even with unbounded preprocessing. 
We describe a randomized algorithm that replies to queries using $\tilde{O}\left(\frac{\sqrt{n}}{\Phi^2}\right)$ probes with no additional memory on regular graphs with conductance $\Phi$ ($n$ is the number of vertices in $G$). In contrast, we show that any deterministic algorithm for regular graphs that uses no memory augmentation requires a linear (in $n$) number of probes, even if the conductance is the largest possible. We give an algorithm for grids and tori that uses a sublinear number of probes and no memory. Last, we give an algorithm for trees that errs on a sublinear number of edges (i.e., a sublinear number of edges are monochromatic under this coloring) that uses sublinear preprocessing, memory and probes per query.