5
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – Huck Bennett
    Aug 13, 2012 at 23:15
  • $\begingroup$ @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. $\endgroup$
    – David Harris
    Aug 13, 2012 at 23:24
  • $\begingroup$ 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. $\endgroup$
    – Huck Bennett
    Aug 13, 2012 at 23:27
  • 3
    $\begingroup$ 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. $\endgroup$
    – SamM
    Aug 13, 2012 at 23:36
  • 1
    $\begingroup$ @Sam I personally think this question belongs at CS@SE, but in any case I think you have the answer $\endgroup$
    – Sasho Nikolov
    Aug 14, 2012 at 0:21

1 Answer 1

Reset to default
6
$\begingroup$

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 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, which run in time $O(\log n + k)$ where $k$ is the size of the query returned.
  • Succinct data structures, which store data in space proportional to the entropy of the stored data
  • Algorithms in the external memory model (section 2 of that in particular--in fact the lecture notes for Erik Demaine's class on Data Structures 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, 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.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.