Merav Parter
Local Computation Algorithms for Spanners
A graph spanner is a fundamental graph structure, which is a sparse
subset of edges of a source graph $G$ that faithfully preserves the
pairwise distances in $G$ up to a small multiplicative stretch. The
common objective in the computation of spanners is to achieve the
best-known existential size-stretch trade-off {\em efficiently}.
Classical models and algorithmic analysis of graph spanners
essentially assume that the algorithm can read the input graph,
perform the computation of the edges contained in the spanner, and
write the answer to the output tape. However, when considering
massive graphs containing millions or even billions of nodes (e.g.,
the underlying graphs of WWW, Facebook and Twitter, and the graphs
used in {\em model checking}), both the input graph and {\em even} the
output spanner might be too large for a single processor to store.
To tackle this challenge, we study {\em local computation algorithms
(LCA)} for graph spanners, where the algorithm should locally decide
whether a given edge $(u,v) \in G$ belongs to the output (sparse)
spanner or not. Such LCAs give the user the ``illusion'' that a
\emph{specific} sparse spanner for the graph is maintained, without
ever fully computing it. We present the following results: (1) For
stretch values $r \in \{2,3\}$, there is an LCA for constructing a
$(2r-1)$-spanner $H \subseteq G$ with $O(n^{1+1/r}\cdot \log n)$
edges, such that given an edge $e \in G$, the LCA answers whether $e
\in H$ by making $o(n^{1-1/2r}\cdot \log n)$ probes to the input
graph. These size/stretch trade-offs are best possible (up to
logarithmic factors). (2) For every $k \geq 2$ and $n$-vertex graph
with maximum degree $O(n^{1/12-\eps})$, there exists a construction of
an $O(k^2)$-spanner $H \subseteq G$ with $\widetilde{O}(n^{1+1/k})$
edges and probe complexity of $\widetilde{O}(n^{1-\eps})$. (3)
Finally, we complement these constructions by providing lower bound
results for the probe complexity of LCAs for the simpler task of {\em
spanning subgraphs}:
Any local algorithm that with success probability of at least $2/3$
maintains a sparse spanner of the input graph with $o(m)$ edges (even
for $k=n$), has probe complexity $\Omega(\min\{\sqrt{n}, n^2/m\})$.
To the best of our knowledge, these are the first LCAs for spanners
with fixed stretch values.
This is joint work with Ronitt Rubinfeld, Ali Vakilian , and Anak Yodpinyanee.