7
$\begingroup$

I am curious if there are graphs problems for which either -

  1. we know that time and/or space complexity is independent of graph sparsity
  2. we do not know whether or not graph sparsity can be exploited to reduce time and/or space complexity

Among many possible notions of the sparsity, I am particularly interested in the one that relies on edge density (or alternatively, average degree).

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ Suppose the problem takes time O(m+n) to solve ? is that considered "independent of the sparsity" ? $\endgroup$
    – Suresh Venkat
    Mar 18, 2012 at 1:44
  • 1
    $\begingroup$ Here is one example - storing all pairs shortest distances is believed to, I think, require $\Omega(n^2)$ space. If this is right, that would be one example. $\endgroup$
    – Rachit
    Mar 18, 2012 at 2:33
  • 5
    $\begingroup$ I see so one thing you might be looking for is a problem where lower bounds depend only on $n$ ? $\endgroup$
    – Suresh Venkat
    Mar 18, 2012 at 2:46
  • 2
    $\begingroup$ for example Johnson's algorithm for all pairs shortest path is $O(V^2 \log V + VE)$ and for sparse graphs e.g when $|E| = O(V)$ it will be $O(V^2 \log V)$, It's not independent from $E$ in general but it's extremely faster than normal ford-falkerson in sparse graphs. $\endgroup$
    – Saeed
    Mar 18, 2012 at 12:00
  • 1
    $\begingroup$ I don't understand. If we know that the time complexity is independent of sparsity, then by definition we know that sparsity cannot be exploited to reduce the time complexity. What am I missing? $\endgroup$
    – Jeffε
    Mar 18, 2012 at 20:36

0

Reset to default

Your Answer

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