Difference between revisions of "Open Problems:14"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
 
(Fixing a typo.)
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{DISPLAYTITLE:Problem 14: Graph Distances}}
+
{{Header
{{Infobox
+
|source=kanpur06
|label1 = Proposed by
+
|who=Andrew McGregor
|data1 = Andrew McGregor
 
|label2 = Source
 
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
 
|label3 = Short link
 
|data3 = 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'' {{cite|FeigenbaumKMSZ-05|FeigenbaumKMSZ-05a|ElkinZ-06|Baswana-06|Elkin-06}} where subgraph $H$ of $G$ is an $(\alpha,\beta)$-spanner
 
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'' {{cite|FeigenbaumKMSZ-05|FeigenbaumKMSZ-05a|ElkinZ-06|Baswana-06|Elkin-06}} where subgraph $H$ of $G$ is an $(\alpha,\beta)$-spanner
Line 13: 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.