# Sparse graphs versus dense graphs

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

• Suppose the problem takes time O(m+n) to solve ? is that considered "independent of the sparsity" ? – Suresh Venkat Mar 18 '12 at 1:44
• 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. – Rachit Mar 18 '12 at 2:33
• I see so one thing you might be looking for is a problem where lower bounds depend only on $n$ ? – Suresh Venkat Mar 18 '12 at 2:46
• 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. – Saeed Mar 18 '12 at 12:00
• 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? – Jeffε Mar 18 '12 at 20:36