<p>As far as I know, there is no published result on computing distances of approximation less than 2 in subquadratic space and sublinear query time. For retrieving approximate distances quickly, you may want to look at results and references in "Faster Algorithms for All-pairs Approximate Shortest Paths" by Baswana and Kavitha (journal version of their FOCS paper has a good review of related work); none of these achieve subquadratic space.</p>

<p>For compactly retrieving approximate distances, you may want to look at the results and references in the above two papers. [As an addition to the answer by Gabor, a word of caution: be careful about the notion of sparsity in above papers -- for approximation $2$, a graph is said to be sparse if $m = o(n^2)$, as you probably know already].</p>

<p>As Sariel pointed out in one of the comments above, a natural lower bound on space for computing distances of approximation less than $2$ is $\Omega(m)$, that is, linear in the size of the graph. If the query time is not bounded, this lower bound can not be improved (trivially, one can use shortest path algorithm by just storing the graph). For constant query time, I know of two lower bounds. First, Patrascu and Roddity had some conditional lower bounds in their FOCS 2010 paper that apply for approximation less than $2$. Second, Sommer et. al. had some lower bounds for extremely sparse graphs. I am not aware of any other (non-trivial) lower bounds.</p>

<p>In terms of upper bounds, the results from above papers do not seem to generalize to approximation less than $2$. We recently made some progress on this problem. The paper should be on ArXiv soon, but if you like, send me an e-mail and I'll be happy to share the paper.</p>

<p>Hope this helps.</p>

<p>~Rachit Agarwal</p>

CC BY-SA 3.0
2011-11-11T22:37:32.530Z
2011-11-11T22:37:32.530Z
Rachit
<p>You might be interested in Rachit Agarwal's 2011 INFOCOM paper:</p>

<p>Rachit Agarwal, P. Brighten Godfrey, Sariel Har-Peled
Approximate Distance Queries and Compact Routing in Sparse Graphs, IEEE INFOCOM 2011</p>

<p>From the abstract:</p>

<p>[For a] graph with average degree $\Theta(\log n)$, special cases of our data structures retrieve stretch 2 paths with $O(n^{3/2})$ space [...] at the cost of $O(\sqrt{n})$ query time.</p>

<p>Note that their distance oracle is only for sparse graphs, but the logarithmic degree bound seems plausible. Added bonus, the algorithm also works for weighted graphs.</p>

CC BY-SA 3.0
2011-11-10T22:29:30.060Z
2011-11-10T22:29:30.060Z
Gabor Retvari
<p>You might also want to take a look at </p>

<p>Pătraşcu, Roditty, <a href="http://people.csail.mit.edu/mip/papers/balls/paper.pdf" rel="nofollow">Distance Oracles Beyond the Thorup--Zwick Bound</a>, FOCS 2010</p>

<p>They have a distance oracle of size $O(n^{5/3})$ with stretch 2. It supports queries in constant time.</p>

CC BY-SA 3.0
2011-11-11T16:20:25.883Z
Thanks! The paper from Agrawal and Mihai does not seem to say anything about approximation "less than" 2, unless I missed something.
Siddhartha
CC BY-SA 3.0
2011-11-11T17:36:12.810Z
It's not, but it might give you an idea about how to obtain a trade-off in order to improve the stretch.
zotachidil
CC BY-SA 3.0
2011-11-10T23:05:08.283Z
2011-11-10T23:05:08.283Z
zotachidil
<p>Given a weighted undirected graph with $m = o(n^2)$ edges, I would like to compute distances of approximation less than 2 between any given pair of vertices. Of course, I would like to use subquadratic space and sublinear query time. </p>

<p>I am aware of Zwick's result that uses matrix multiplication, but I am curious if any combinatorial algorithms are known for this problem?</p>

CC BY-SA 3.0
2011-11-10T18:26:09.590Z
Hi @Siddhartha, I'm sorry if this is a dumb question: [Zwick's result](http://arxiv.org/abs/cs/0008011) seems to use quadratic space, is that correct?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-11-10T18:33:15.573Z
Also, is additive error allowed?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-11-10T21:52:19.540Z
@Hsien-ChihChang張顯之 - I was interested in results on multiplicative approximation only. The case of additive approximation may be interesting in its own right - easier for dense graphs, I guess. One can use a spanner and get additive approximation for dense enough graphs. For sparse graphs, as far as I know, spanners would not help.
Siddhartha
CC BY-SA 3.0
2011-11-10T22:09:08.430Z
@Hsien-ChihChang張顯之 - Interesting! I am not sure - I guess you'll need quadratic space to write down the matrices; for some reason I thought you could avoid that. That's another questions now - does Zwick's result require quadratic space?
Siddhartha
CC BY-SA 3.0
2011-11-11T04:10:19.977Z
Thank you for the reply! In the article [Approximate Distance Oracles](http://www.cs.tau.ac.il/~zwick/papers/oracle-JACM-revision.ps) by Thorup and Zwick, they claimed that the space usage of the one in Zwick'02 is quadratic, and any distance oracle with stretch less than $2k+1$ implies an $\Omega(n^{1+1/k})$ space lowerbound for any integer $k$ by the girth conjecture. So maybe even for stretch 2 a subquadratic space distance oracle is impossible. For lowerbounds the following paper might also be useful: 
[Distance Oracles for Sparse Graphs](http://www.weiyu.org/papers/ds.pdf).
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-11-11T04:23:45.983Z
Thanks for the reply @Hsien-ChihChang張顯之 - I modified the question (with an upper bound on the number of edges in the graph) -- their lower bound, I believe, does not say anything non-trivial if the graph has $o(n^2)$ edges.
Siddhartha
CC BY-SA 3.0
2011-11-11T04:56:46.877Z
Doesn't the following argument works? Consider any graph $G$ with $n$ vertices and $m$ edges. Consider all the weights of the edges to be $1$. any distance oracle that can do strictly better approximation than $2$, can be used to decide for every possible edge, whether or not it is in the graph. But that of course implies that such a distance oracle must use $\Omega(m)$ bits. No? (The argument is a bit handwavy but should be correct.) (Formally, the number of bits is $\log_2 \binom{N}{m}$, where $N=\binom{n}{2}$. This is $\geq m \log_2 (N/m)$.
Sariel Har-Peled
CC BY-SA 3.0
2011-11-11T16:18:56.200Z
Thanks Sariel - it may be possible to derive a $\Omega(m)$ lower bound but I am fine with that. All I would like to have is subquadratic space and sublinear query time. For graphs with $m = o(n^2)$ edges, $\Omega(m)$ lower bound does not say anything for the problem -- is that right?
Siddhartha
<ds.algorithms><graph-algorithms>
Computing distances with approximation less than 2 in general graphs?
Siddhartha
# Computing distances with approximation less than 2 in general graphs?

(Asked by: username_0 on 2011-11-10)

Given a weighted undirected graph with $m = o(n^2)$ edges, I would like to compute distances of approximation less than 2 between any given pair of vertices. Of course, I would like to use subquadratic space and sublinear query time.

I am aware of Zwick's result that uses matrix multiplication, but I am curious if any combinatorial algorithms are known for this problem?

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: Hi @Siddhartha, I'm sorry if this is a dumb question: [Zwick's result](http://arxiv.org/abs/cs/0008011) seems to use quadratic space, is that correct?  
> **username_1**: Also, is additive error allowed?  
> **username_0**: @Hsien-ChihChang張顯之 - I was interested in results on multiplicative approximation only. The case of additive approximation may be interesting in its own right - easier for dense graphs, I guess. One can use a spanner and get additive approximation for dense enough graphs. For sparse graphs, as far as I know, spanners would not help.  
> **username_0**: @Hsien-ChihChang張顯之 - Interesting! I am not sure - I guess you'll need quadratic space to write down the matrices; for some reason I thought you could avoid that. That's another questions now - does Zwick's result require quadratic space?  
> **username_1**: Thank you for the reply! In the article [Approximate Distance Oracles](http://www.cs.tau.ac.il/~zwick/papers/oracle-JACM-revision.ps) by Thorup and Zwick, they claimed that the space usage of the one in Zwick'02 is quadratic, and any distance oracle with stretch less than $2k+1$ implies an $\Omega(n^{1+1/k})$ space lowerbound for any integer $k$ by the girth conjecture. So maybe even for stretch 2 a subquadratic space distance oracle is impossible. For lowerbounds the following paper might also be useful:  [Distance Oracles for Sparse Graphs](http://www.weiyu.org/papers/ds.pdf).  
> **username_0**: Thanks for the reply @Hsien-ChihChang張顯之 - I modified the question (with an upper bound on the number of edges in the graph) -- their lower bound, I believe, does not say anything non-trivial if the graph has $o(n^2)$ edges.  
> **username_2**: Doesn't the following argument works? Consider any graph $G$ with $n$ vertices and $m$ edges. Consider all the weights of the edges to be $1$. any distance oracle that can do strictly better approximation than $2$, can be used to decide for every possible edge, whether or not it is in the graph. But that of course implies that such a distance oracle must use $\Omega(m)$ bits. No? (The argument is a bit handwavy but should be correct.) (Formally, the number of bits is $\log_2 \binom{N}{m}$, where $N=\binom{n}{2}$. This is $\geq m \log_2 (N/m)$.  
> **username_0**: Thanks Sariel - it may be possible to derive a $\Omega(m)$ lower bound but I am fine with that. All I would like to have is subquadratic space and sublinear query time. For graphs with $m = o(n^2)$ edges, $\Omega(m)$ lower bound does not say anything for the problem -- is that right?  

---

## 3 answers

### Answer by username_3 on 2011-11-11. Score: 6

As far as I know, there is no published result on computing distances of approximation less than 2 in subquadratic space and sublinear query time. For retrieving approximate distances quickly, you may want to look at results and references in "Faster Algorithms for All-pairs Approximate Shortest Paths" by Baswana and Kavitha (journal version of their FOCS paper has a good review of related work); none of these achieve subquadratic space.

For compactly retrieving approximate distances, you may want to look at the results and references in the above two papers. [As an addition to the answer by Gabor, a word of caution: be careful about the notion of sparsity in above papers -- for approximation $2$, a graph is said to be sparse if $m = o(n^2)$, as you probably know already].

As Sariel pointed out in one of the comments above, a natural lower bound on space for computing distances of approximation less than $2$ is $\Omega(m)$, that is, linear in the size of the graph. If the query time is not bounded, this lower bound can not be improved (trivially, one can use shortest path algorithm by just storing the graph). For constant query time, I know of two lower bounds. First, Patrascu and Roddity had some conditional lower bounds in their FOCS 2010 paper that apply for approximation less than $2$. Second, Sommer et. al. had some lower bounds for extremely sparse graphs. I am not aware of any other (non-trivial) lower bounds.

In terms of upper bounds, the results from above papers do not seem to generalize to approximation less than $2$. We recently made some progress on this problem. The paper should be on ArXiv soon, but if you like, send me an e-mail and I'll be happy to share the paper.

Hope this helps.

~Rachit Agarwal


---

### Answer by username_4 on 2011-11-10. Score: 5

You might be interested in Rachit Agarwal's 2011 INFOCOM paper:

Rachit Agarwal, P. Brighten Godfrey, Sariel Har-Peled
Approximate Distance Queries and Compact Routing in Sparse Graphs, IEEE INFOCOM 2011

From the abstract:

[For a] graph with average degree $\Theta(\log n)$, special cases of our data structures retrieve stretch 2 paths with $O(n^{3/2})$ space [...] at the cost of $O(\sqrt{n})$ query time.

Note that their distance oracle is only for sparse graphs, but the logarithmic degree bound seems plausible. Added bonus, the algorithm also works for weighted graphs.


---

### Answer by username_5 on 2011-11-10. Score: 3

You might also want to take a look at

Pătraşcu, Roditty, [Distance Oracles Beyond the Thorup--Zwick Bound](http://people.csail.mit.edu/mip/papers/balls/paper.pdf), FOCS 2010

They have a distance oracle of size $O(n^{5/3})$ with stretch 2. It supports queries in constant time.

> **Comments:**
> **username_0**: Thanks! The paper from Agrawal and Mihai does not seem to say anything about approximation "less than" 2, unless I missed something.  
> **username_5**: It's not, but it might give you an idea about how to obtain a trade-off in order to improve the stretch.  

---

