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

Question

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

Answer 1

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.

Answer 2

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.

See also my answer what is easy for minor-excluded graphs? for further related comments.

Answer 3

I can't think of any graph property that has had as much impact on the design of efficient algorithms as bounded treewidth, and bidimensionality in general.

Answer 4

One can think of a graph as an adjacency matrix - there are several definitions for matrix sparsity (% of zero entries, for example) which could translate back to the graph itself. Other than % of zero entries, matrix bandwidth under a reordering could be a good proxy for graph sparsity (it looks like bandwidth is related to degeneracy).