11
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Hi @Siddhartha, I'm sorry if this is a dumb question: Zwick's result seems to use quadratic space, is that correct? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Nov 10, 2011 at 18:26
  • 1
    $\begingroup$ Also, is additive error allowed? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Nov 10, 2011 at 18:33
  • $\begingroup$ @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. $\endgroup$
    – Siddhartha
    Commented Nov 10, 2011 at 21:52
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Sariel Har-Peled
    Commented Nov 11, 2011 at 4:56
  • 1
    $\begingroup$ 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? $\endgroup$
    – Siddhartha
    Commented Nov 11, 2011 at 16:18

3 Answers 3

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

You might also want to take a look at

Pătraşcu, Roditty, Distance Oracles Beyond the Thorup--Zwick Bound, FOCS 2010

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! The paper from Agrawal and Mihai does not seem to say anything about approximation "less than" 2, unless I missed something. $\endgroup$
    – Siddhartha
    Commented Nov 11, 2011 at 16:20
  • $\begingroup$ It's not, but it might give you an idea about how to obtain a trade-off in order to improve the stretch. $\endgroup$
    – zotachidil
    Commented Nov 11, 2011 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.