<p>I am curious if there are graphs problems for which either -</p>

<ol>
<li>we know that time and/or space complexity is independent of graph sparsity</li>
<li>we do not know whether or not graph sparsity can be exploited to reduce time and/or space complexity</li>
</ol>

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

CC BY-SA 3.0
2012-03-18T01:44:45.187Z
Suppose the problem takes time O(m+n) to solve ? is that considered "independent of the sparsity" ?
Suresh Venkat
CC BY-SA 3.0
2012-03-18T02:32:19.203Z
@SureshVenkat - I'd say that is not independent of the sparsity -- time complexity improves as the graph gets sparser.
Rachit
CC BY-SA 3.0
2012-03-18T02:33:43.460Z
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
CC BY-SA 3.0
2012-03-18T02:46:37.500Z
I see so one thing you might be looking for is a problem where lower bounds depend only on $n$ ?
Suresh Venkat
CC BY-SA 3.0
2012-03-18T09:39:19.890Z
Yes, problems for which lower and upper bounds are independent of $m$ would be interesting.
Rachit
CC BY-SA 3.0
2012-03-18T12:00:02.833Z
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
CC BY-SA 3.0
2012-03-18T20:36:01.480Z
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ε
CC BY-SA 3.0
2012-03-18T21:15:49.230Z
@Jeff - I am looking for problems for which either 1 holds or 2 holds.
Rachit
CC BY-SA 3.0
2012-03-19T12:26:11.250Z
There are NP-complete problems that remain NPC even for cubic graphs. Does this count as an example for 1?
Vinicius dos Santos
CC BY-SA 3.0
2012-09-06T04:38:06.147Z
it depends how you define "sparse". if its a small constant fraction then one answer is in this question [hardness of parameterized clique](http://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique). also, equivalently, monotone circuit theory states that many NP complete problems (incl SAT, clique detection) have NP complete "slices" which are inputs with the same number of 1's. also relevant, [mahaney's thm](http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute-to-mahaney.html) that says there are no NP complete sparse sets unless P==NP
vzn
<ds.algorithms><graph-theory><graph-algorithms>
Sparse graphs versus dense graphs
Rachit
# Sparse graphs versus dense graphs

(Asked by: username_0 on 2012-03-17)

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Suppose the problem takes time O(m+n) to solve ? is that considered "independent of the sparsity" ?  
> **username_0**: @SureshVenkat - I'd say that is not independent of the sparsity -- time complexity improves as the graph gets sparser.  
> **username_0**: 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.  
> **username_1**: I see so one thing you might be looking for is a problem where lower bounds depend only on $n$ ?  
> **username_0**: Yes, problems for which lower and upper bounds are independent of $m$ would be interesting.  
> **username_2**: 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.  
> **username_3**: 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?  
> **username_0**: @Jeff - I am looking for problems for which either 1 holds or 2 holds.  
> **username_4**: There are NP-complete problems that remain NPC even for cubic graphs. Does this count as an example for 1?  
> **username_5**: it depends how you define "sparse". if its a small constant fraction then one answer is in this question [hardness of parameterized clique](http://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique). also, equivalently, monotone circuit theory states that many NP complete problems (incl SAT, clique detection) have NP complete "slices" which are inputs with the same number of 1's. also relevant, [mahaney's thm](http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute-to-mahaney.html) that says there are no NP complete sparse sets unless P==NP  

---

## 0 answers

