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).

  • 2
    $\begingroup$ Suppose the problem takes time O(m+n) to solve ? is that considered "independent of the sparsity" ? $\endgroup$ – Suresh Venkat Mar 18 '12 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 '12 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 '12 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 '12 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 '12 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.