# What is the most important notion of sparsity for the design of efficient graph algorithms?

There are several competing notions of a "sparse graph". For instance, a surface-embeddable graph could be considered sparse. Or a graph with bounded edge density. Or a graph with high girth. A graph with large expansion. A graph with bounded treewidth. (Even within the subfield of random graphs, it is slightly ambiguous as to what could be called sparse.) Et cetera.

What notion of "sparse graph" has had the most impact on the design of efficient graph algorithms, and why? Similarly, what notion of "dense graph" ... ? (NB: Karpinski has worked a great deal on approximation results for one standard model of dense graphs.)

I have just seen a talk by J. Nesetril on a program of his (together with P. Ossona de Mendez) to capture measures of sparsity in graphs within a unified (asymptotic) framework. My question -- yes, maybe quite subjective and I expect different camps -- is motivated by the desire to catch a multi-faceted perspective on the use of sparsity in algorithms (and plug any gaps in my own understanding of the issue).

• Do you think a complete graph is also sparse? Complete graphs have large expansion and bounded cliquewidth. Apr 13 '11 at 14:58
• @Yoshio Okamoto: good point -- I suppose treewidth would have been a better choice there...
– RJK
Apr 13 '11 at 15:02
• The program of J. Nesetril and P. Ossona de Mendez you mentioned is now a book. Jan 23 '13 at 9:35

I think that by any reasonable standard an n × n × n three-dimensional grid graph would have to be considered sparse, and that rules out most candidate definitions involving surface embeddings or minors. (Sublinear treewidth would still be possible, though.)

My current favorite sparsity measure is degeneracy. The degeneracy of a graph is the minimum, over all linear orderings of the vertices of the graph, of the maximum outdegree in the directed acyclic orientation of the graph formed by orienting each edge from earlier to later vertices in the ordering. Equivalently, it's the maximum, over all subgraphs, of the minimum degree in the subgraph. So for instance planar graphs have degeneracy five because any subgraph of a planar graph has a vertex of degree at most five. Degeneracy is easy to calculate in linear time, and the linear ordering that comes from the definition is useful in algorithms.

Degeneracy is within a constant factor of some other standard measures including arboricity, thickness, and the maximum average degree of any subgraph, but those are I think harder to use.

• This is quite a nice answer. It highlights how seemingly simple structures like grids can often cause mischief when thinking about sparse graphs. (I guess it is not too surprising given how important grid minors are to Robertson-Seymour theory.) Would it be fair to say that degeneracy is to the greedy algorithm as treewidth is to dynamic programming? Or maybe there is more to say about sparsity measures that imply good orderings, e.g. pathwidth?
– RJK
Apr 14 '11 at 8:46
• @RJK: To take this argument to its extreme, 3-regular planar grids (hexagonal grids/wall graphs) have unbounded treewidth but are about as sparse as one can get. Apr 14 '11 at 19:41
• @Andras: Of course, but how about a graph with small treewidth that is not sparse? In this (one-way) sense, I think treewidth qualifies as a sparsity measure too.
– RJK
Apr 15 '11 at 8:16
• @RJK: Interesting. Is a $k$-regular tree with $n$ vertices still sparse, if $k$ is say $\Omega(\log n)$ and the depth is $\Theta(\log n/\log \log n)$? Apr 15 '11 at 17:57

There do seem to be many "good" notions of sparsity, but there is something of a hierarchy for those structural notions of sparsity that have a model-theoretic flavour. I think these have had a strong impact on efficient graph algorithms.

Martin Grohe in his in-progress monograph Descriptive Complexity, Canonisation, and Definable Graph Structure Theory discusses classes of graphs that exclude some minor. These classes are sparse because they cannot have very dense subgraphs. Excluded minors generalise many known reasons for tractability, including bounded treewidth (treewidth at most $k$ is achieved by excluding $K_{k+2}$ as a minor).

Anuj Dawar's course notes from November 2010 also discuss locally bounded treewidth, which is incomparable with excluded minors. Bounded degree clearly defines sparse graphs, and such graphs have bounded local treewidth, but are not definable by a set of excluded minors.

The impact of bounded degree is clear: it is often one of the first restrictions shown to make a hard problem tractable, for instance Luks' algorithm for Graph Isomorphism on bounded-degree graphs. The impact of excluding a minor is also clear, at least in the guise of bounded treewidth (as Suresh pointed out).

The notion of locally excluding a minor generalises both locally bounded treewidth and excluded minors, so forming the "most general" class in the hierarchy. However, it is not yet clear how to make use of this property in practical algorithms. Even the "tractable" case of excluding a minor does not necessarily have good practical algorithms; large constants abound in the model-theoretic algorithms. I do hope some of these classes will turn out to have practically efficient algorithms in the long run.