<p>Even when stored very efficiently, vertices with zero degree must be stored in some nonzero space (otherwise, how can we say they even exist)?  That said, they can be stored and searched more efficiently than $O(|V| + |E|)$ using similar ideas to what you describe.</p>

<p>For example, you could just take a <a href="http://www.algorithmist.com/index.php/Graph_data_structures">standard data structure for storing graphs</a> and store the set of nodes $V' \subseteq V$ which have degree greater than 0.  We don't need to store any information about $V_0$, the set of nodes with degree 0, except for how many there are.</p>

<p>In other words, in a graph with vertices $V$ and edges $E$, if we define</p>

<p>$V' = \{v\in V | v \mbox{ has degree} &gt; 0\}$</p>

<p>$V_0 = \{v\in V | v \mbox{ has degree }  0\}$</p>

<p>We can store the nodes with nonzero degree in $O(|V'| + |E|)$ space, and the nodes with zero degree in $O(\log |V_0|)$ space, giving a total of $O(|V'| + |E| + \log |V_0|)$ space.  </p>

<p>Many algorithms that run in linear time, for example BFS and DFS, will run in time $O(|V'| + |E|)$ because the algorithm can just ignore the vertices with degree zero.  Like you say, if $n &gt;&gt; m$, this is much more efficient than the standard algorithm.</p>

<p>There are many cases where algorithms are parameterized by factors in addition to the size of the input.  Other examples of this include </p>

<ul>
<li>Output-sensitive algorithms like range queries for <a href="http://en.wikipedia.org/wiki/Range_tree">range trees</a>, which run in time $O(\log n + k)$ where $k$ is the size of the query returned.  </li>
<li><a href="http://en.wikipedia.org/wiki/Succinct_data_structure">Succinct data structures</a>, which store data in space proportional to the entropy of the stored data</li>
<li>Algorithms in the <a href="http://courses.csail.mit.edu/6.851/spring12/scribe/lec7.pdf">external memory model</a> (section 2 of that in particular--in fact the lecture notes for <a href="http://courses.csail.mit.edu/6.851/spring12/lectures/">Erik Demaine's class on Data Structures</a> deal with most of these concepts) depend on the size of a cache and the size of a block transferred from the cache to the processor.</li>
<li><a href="http://en.wikipedia.org/wiki/Sparse_matrix">Sparse matrix data structures</a>, and similar structures and algorithms for sparse graphs, which are probably the most similar to what you're asking about.</li>
</ul>

<p>Most of the references here are fairly general/low level, but there are a great deal of research papers on many of these topics.  In any case, there are sometimes good reasons to use another parameter while analyzing an algorithm's running time, but for general algorithms like DFS, it's assumed that no special data structure or storage methodology is used, leading to $O(|V| + |E|)$ time.</p>

CC BY-SA 3.0
2012-08-14T06:28:37.063Z
2012-08-14T06:28:37.063Z
SamM
<p>It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.).</p>

<p>For nearly all such algorithms, vertices of degree zero have no effect on the underlying graph problem. So a solution to the graph problem can usually treat all these unsupported vertices jointly, and does not need to process them individually. For example, in depth-first-search, it suffices to list the dfs-tree for the supported vertices, along with an auxiliary record that all other vertices are unsupported.</p>

<p>If the graph is presented with any kind of intelligent data structure, it should be possible to process in time $O(m)$, and to generate a data structure that encodes the solution in time $O(m)$. This applies even in the case that $n \gg m$.</p>

<p>My question is, what is the reason for the notation $O(m+n)$? Are there really algorithms which require this running time $\Omega(n)$ in the regime $n \gg m$? Is this basically for pedagogical purposes only?</p>

CC BY-SA 3.0
2012-08-13T23:15:48.733Z
Assuming $m$ is the number of edges and $n$ the number of vertices... "Any kind of intelligent data structure" I guess rules out an adjacency list. In general, yes, $O(m+n)$ is necessary because both $m = o(n)$ and $m = \omega(n)$ are possible.
Huck Bennett
CC BY-SA 3.0
2012-08-13T23:24:45.113Z
@Huck, the question is, how are null vertices represented in the adjacency list? If you simply list, for each vertex, all of its neighbors, then null vertices take zero space to store and process.
David Harris
CC BY-SA 3.0
2012-08-13T23:27:00.970Z
Ah, well that depends on how you store it - if you use a list of lists or an array of lists, etc. In any case it doesn't matter - let me change "I guess rules out an adjacency list" to "I guess rules out an adjacency matrix" and the same issue remains.
Huck Bennett
CC BY-SA 3.0
2012-08-13T23:36:37.527Z
A null vertex can never take zero space because then you don't know how many there are; they might as well not exist.  One could possibly use a standard data structure (such as an adjacency matrix or a list of arcs) with the number ofzero-degree vertices.  This only takes $O(n_{full} + \log n_{empty} + m)$ space and many linear graph algorithms would run in that much time.  But in the worst case, $n_{empty} = 0$.  

In any case it's often possible to paramaterize algorithms with additional variables and gain more precise running time, but these possibilities are often ignored for simplicity.
SamM
CC BY-SA 3.0
2012-08-13T23:42:05.683Z
@Sam: What do $n_{full}$ and $n_{empty}$ mean?
Huck Bennett
CC BY-SA 3.0
2012-08-13T23:44:57.367Z
$n_{full}$ = number of vertices with nonzero degree

$n_{empty}$ = number of vertices with zero degree

Sorry wanted to explain but ran out of space
SamM
CC BY-SA 3.0
2012-08-14T00:21:52.717Z
@Sam I personally think this question belongs at CS@SE, but in any case I think you have the answer
Sasho Nikolov
CC BY-SA 3.0
2012-08-14T05:31:46.427Z
@Sam: Also, I'd recommend making this answer so the question doesn't reappear every month
Suresh Venkat
<ds.algorithms><terminology><asymptotics>
$O(m+n)$ really necessary for graph algorithms?
David Harris
# $O(m+n)$ really necessary for graph algorithms?

(Asked by: username_0 on 2012-08-13)

It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.).

For nearly all such algorithms, vertices of degree zero have no effect on the underlying graph problem. So a solution to the graph problem can usually treat all these unsupported vertices jointly, and does not need to process them individually. For example, in depth-first-search, it suffices to list the dfs-tree for the supported vertices, along with an auxiliary record that all other vertices are unsupported.

If the graph is presented with any kind of intelligent data structure, it should be possible to process in time $O(m)$, and to generate a data structure that encodes the solution in time $O(m)$. This applies even in the case that $n \gg m$.

My question is, what is the reason for the notation $O(m+n)$? Are there really algorithms which require this running time $\Omega(n)$ in the regime $n \gg m$? Is this basically for pedagogical purposes only?

**Tags:** ds.algorithms, terminology, asymptotics

> **Comments:**
> **username_1**: Assuming $m$ is the number of edges and $n$ the number of vertices... "Any kind of intelligent data structure" I guess rules out an adjacency list. In general, yes, $O(m+n)$ is necessary because both $m = o(n)$ and $m = \omega(n)$ are possible.  
> **username_0**: @Huck, the question is, how are null vertices represented in the adjacency list? If you simply list, for each vertex, all of its neighbors, then null vertices take zero space to store and process.  
> **username_1**: Ah, well that depends on how you store it - if you use a list of lists or an array of lists, etc. In any case it doesn't matter - let me change "I guess rules out an adjacency list" to "I guess rules out an adjacency matrix" and the same issue remains.  
> **username_2**: A null vertex can never take zero space because then you don't know how many there are; they might as well not exist.  One could possibly use a standard data structure (such as an adjacency matrix or a list of arcs) with the number ofzero-degree vertices.  This only takes $O(n_{full} + \log n_{empty} + m)$ space and many linear graph algorithms would run in that much time.  But in the worst case, $n_{empty} = 0$.    In any case it's often possible to paramaterize algorithms with additional variables and gain more precise running time, but these possibilities are often ignored for simplicity.  
> **username_1**: @Sam: What do $n_{full}$ and $n_{empty}$ mean?  
> **username_2**: $n_{full}$ = number of vertices with nonzero degree  $n_{empty}$ = number of vertices with zero degree  Sorry wanted to explain but ran out of space  
> **username_3**: @Sam I personally think this question belongs at CS@SE, but in any case I think you have the answer  
> **username_4**: @Sam: Also, I'd recommend making this answer so the question doesn't reappear every month  

---

## 1 answers

### Answer by username_2 on 2012-08-14. Score: 6

Even when stored very efficiently, vertices with zero degree must be stored in some nonzero space (otherwise, how can we say they even exist)? That said, they can be stored and searched more efficiently than $O(|V| + |E|)$ using similar ideas to what you describe.

For example, you could just take a [standard data structure for storing graphs](http://www.algorithmist.com/index.php/Graph_data_structures) and store the set of nodes $V' \subseteq V$ which have degree greater than 0. We don't need to store any information about $V\_0$, the set of nodes with degree 0, except for how many there are.

In other words, in a graph with vertices $V$ and edges $E$, if we define

$V' = \{v\in V | v \mbox{ has degree} > 0\}$

$V\_0 = \{v\in V | v \mbox{ has degree } 0\}$

We can store the nodes with nonzero degree in $O(|V'| + |E|)$ space, and the nodes with zero degree in $O(\log |V\_0|)$ space, giving a total of $O(|V'| + |E| + \log |V\_0|)$ space.

Many algorithms that run in linear time, for example BFS and DFS, will run in time $O(|V'| + |E|)$ because the algorithm can just ignore the vertices with degree zero. Like you say, if $n >> m$, this is much more efficient than the standard algorithm.

There are many cases where algorithms are parameterized by factors in addition to the size of the input. Other examples of this include

* Output-sensitive algorithms like range queries for [range trees](http://en.wikipedia.org/wiki/Range_tree), which run in time $O(\log n + k)$ where $k$ is the size of the query returned.
* [Succinct data structures](http://en.wikipedia.org/wiki/Succinct_data_structure), which store data in space proportional to the entropy of the stored data
* Algorithms in the [external memory model](http://courses.csail.mit.edu/6.851/spring12/scribe/lec7.pdf) (section 2 of that in particular--in fact the lecture notes for [Erik Demaine's class on Data Structures](http://courses.csail.mit.edu/6.851/spring12/lectures/) deal with most of these concepts) depend on the size of a cache and the size of a block transferred from the cache to the processor.
* [Sparse matrix data structures](http://en.wikipedia.org/wiki/Sparse_matrix), and similar structures and algorithms for sparse graphs, which are probably the most similar to what you're asking about.

Most of the references here are fairly general/low level, but there are a great deal of research papers on many of these topics. In any case, there are sometimes good reasons to use another parameter while analyzing an algorithm's running time, but for general algorithms like DFS, it's assumed that no special data structure or storage methodology is used, leading to $O(|V| + |E|)$ time.


---

