Problem 14: Graph Distances

Proposed by	Andrew McGregor
Source	Kanpur 2006
Short link	http://sublinear.info/14

Given a stream of edges defining a graph $G$, how well can we estimate $d_G(u,v)$, the length of the shortest path between two nodes $u$ and $v$? Progress that has been made on this problem is based on constructing spanners [FeigenbaumKMSZ-05,FeigenbaumKMSZ-05a,ElkinZ-06,Baswana-06,Elkin-06] where subgraph $H$ of $G$ is an $(\alpha,\beta)$-spanner for $G$ if \[\forall x,y \in V, \ d_G(x,y)\le d_H(x,y) \le \alpha \cdot d_G(x,y)+\beta \enspace .\] Clearly, an $(\alpha,\beta)$-spanner gives an $\alpha+\beta/d_G(u,v)$ approximation to $d_G(u,v)$. Since a spanner is constructed independently of $u$ and $v$ it is perhaps surprising that this approach gives nearly optimal results for approximating $d_G(u,v)$ in a single pass [FeigenbaumKMSZ-05]. It is unclear whether there is a better approach for multiple pass algorithms. Clearly, $d_G(u,v)$ can be computed exactly in $d_G(u,v)$ passes but for $d_G(u,v)$ large this is infeasible. Can we do better? For example, how well can $d_G(u,v)$ be approximated in $O(\log n)$ passes? What if the edges arrived in random order?