Difference between revisions of "Open Problems:14"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Fixing a typo.)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Graph Distances
 
 
|source=kanpur06
 
|source=kanpur06
 
|who=Andrew McGregor
 
|who=Andrew McGregor
Line 9: Line 8:
 
Clearly, an $(\alpha,\beta)$-spanner gives an $\alpha+\beta/d_G(u,v)$ approximation to $d_G(u,v)$.
 
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 {{cite|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?
 
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 {{cite|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?
 +
 +
== Update ==
 +
Guruswami and Onak {{cite|GuruswamiO-13}} showed that checking if $d_G(u,v) \le 2(p+1)$ in $p$ passes, where $p = O\left(\frac{\log n}{\log\log n}\right)$, requires $\Omega\left(\frac{n^{1+1/(2p+2)}}{p^{20}\log^{3/2}n}\right)$ bits of space.

Latest revision as of 22:17, 25 September 2016

Suggested by Andrew McGregor
Source Kanpur 2006
Short link https://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?

Update[edit]

Guruswami and Onak [GuruswamiO-13] showed that checking if $d_G(u,v) \le 2(p+1)$ in $p$ passes, where $p = O\left(\frac{\log n}{\log\log n}\right)$, requires $\Omega\left(\frac{n^{1+1/(2p+2)}}{p^{20}\log^{3/2}n}\right)$ bits of space.