The origin of the notion of treewidth

Question

My question today is (as usual) a bit silly; but I would request you to kindly consider it.

I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that it is used in FPT algorithms, but I do not think that that was the reason why this notion was defined.

I have written up the scribe notes on this topic in the class of Prof Robin Thomas. I think I understand some of the applications of this concept (as in it transfers separation properties of the tree to the graph decomposed), but for some reason I am not really convinced that the reason this concept was developed was to measure closeness of a graph to a tree.

I will try to make myself more clear (I am not sure if I can, please let me know if the question is not clear). I would like to know if similar notions existed elsewhere in some other branch of mathematics from where this notion was supposedly "borrowed". My guess will be topology -- but owing to my lack of background, I cannot say anything.

The primary reason as to why I am curious about this would be -- the first time I read its definition, I was not sure why and how would anyone conceive of it and to what end. If the question is not still clear I would finally try stating it this way - Let us pretend the notion of treewidth did not exist. What natural questions (or extensions of some mathematical theorems/concepts) to discrete settings will lead one to conceive of a definition (let me use the word involved) as treewidth's.

Answer 1

If you really want to know what led Neil Robertson and me to tree-width, it wasn't algorithms at all. We were trying to solve Wagner's conjecture that in any infinite set of graphs, one of them is a minor of another, and we were right at the beginning. We knew it was true if we restricted to graphs with no k-vertex path; let me explain why. We knew all such graphs had a simple structure (more exactly, every graph with no k-vertex path has this structure, and every graph with this structure has no 2^k-vertex path); and we knew that in every infinite set of graphs all with this structure, one of them was a minor of another. So Wagner's conjecture was true for graphs with a bound on their maximum path length.

We also knew it was true for graphs with no k-star as a minor, again because we had a structure theorem for such graphs. We tried to look for more general minors that had corresponding structure theorems that we could use to prove Wagner's conjecture, and that led us to path-width; exclude ANY tree as a minor and you get bounded path-width, and if you have bounded path-width then there are trees you can't have as a minor. (That was a hard theorem for us; we had a tremendously hard proof in the first Graph Minors paper, don't read it, it can be made much easier.) But we could prove Wagner's conjecture for graphs with bounded path-width, and that meant it was true for graphs not containing any fixed tree as a minor; a big generalization of the path and star cases I mentioned earlier.

Anyway, with that done we tried to get further. We couldn't do general graphs, so we thought about planar graphs. We found a structure theorem for the planar graphs that did not contain any fixed planar graph as a minor (this was easy); it was bounded tree-width. We proved that for any fixed planar graph, all the planar graphs that did not contain it as a minor had bounded tree-width. As you can imagine, that was really exciting; by coincidence, the structure theorem for excluding planar graphs (inside bigger planar graphs) was a natural twist on the structure theorem for excluding trees (inside general graphs). We felt we were doing something right. And that let us prove Wagner's conjecture for all planar graphs, because we had this structure theorem.

Since tree-width worked for excluding planar graphs inside bigger planar graphs, it was a natural question whether it worked for excluding planar graphs inside non-planar graphs -- was it true that for every fixed planar graph, all graphs not containing it as a minor had bounded tree-width? This we couldn't prove for a long time, but that's how we got to thinking about tree-width of general graphs. And once we had the concept of tree-width, it was pretty clear that it was good for algorithms. (And yes, we had no idea that Halin had thought about tree-width already.)

Answer 2

Here's how you could come up with tree-width concept yourself.

Suppose you want to count the number of independent sets in the following graph.

Independent sets can be partitioned into ones where top node is occupied, and ones where it is unoccupied

Now, notice that knowing whether top node is occupied, you can count number of independent sets in each subproblem separately, and multiply them. Repeating this process recursively gives you an algorithm to count independent sets based on graph separators.

Now, suppose you no longer have a tree. This means separators are bigger, but you can use the same idea. Consider counting independent sets in the following graph.

Use the same idea of breaking the problem into subproblems on the separator you get the following

Like in the previous example, each term in the sum decomposes into two smaller counting tasks across the separator.

Note that we have more terms in the sum than in the previous example because we have to enumerate over all configurations on our separator, which can potentially grow exponentially with size of the separator (size 2 in this case).

Tree decomposition is a data-structure to compactly store these recursive partitioning steps. Consider the following graph and its tree decomposition

To count using this decomposition you'd first fix values in nodes 3,6 which breaks it into 2 subproblems. In the first subproblem you'd additionally fix node 5, which breaks its part into two smaller subparts.

Size of the largest separator in an optimal recursive decomposition is precisely the tree width. For larger counting problems, size of the largest separator dominates the runtime, which is why this quantity is so important.

As to the notion of tree-width measuring how close graph is to a tree, one way to make it intuitive is to look at the alternative derivation of tree decomposition -- from correspondence with chordal graphs. First triangulate the graph by traversing vertices in order and interconnecting all "higher ordered" neighbors of each vertex.

Then construct tree decomposition by taking maximal cliques and connecting them iff their intersection is a maximal separator.

Recursive separator and triangulation based approaches of constructing tree decomposition are equivalent. Tree width+1 is the size of the largest clique in optimal triangulation of the graph, or if the graph is already triangulated, just size of the largest clique.

So in a sense, chordal graphs of treewidth tw can be thought of as trees where instead of single nodes we have overlapping cliques of size at most tw+1. Non-chordal graphs are such "clique trees" with some clique edges missing

Here are some chordal graphs and their tree-width.

Answer 3

I believe treewidth itself started with the Robertson Seymour paper already given. But some earlier precursors appear to be:

• The concept of a "dimension" of a graph that would control the behavior of dynamic proogramming algorithms on it, from Bertelé, Umberto; Brioschi, Francesco (1972), Nonserial Dynamic Programming.

• The concept of pursuit-evasion games on graphs, from Parsons, T. D. (1976). "Pursuit-evasion in a graph". Theory and Applications of Graphs. Springer-Verlag. pp. 426–441. One variant of this was much later shown to be equivalent to treewidth: Seymour, Paul D.; Thomas, Robin (1993), "Graph searching and a min-max theorem for tree-width", Journal of Combinatorial Theory, Series B 58 (1): 22–33, doi:10.1006/jctb.1993.1027.

• Separator hierarchies for planar graphs, starting from Ungar, Peter (1951), "A theorem on planar graphs", Journal of the London Mathematical Society 1 (4): 256, doi:10.1112/jlms/s1-26.4.256, and continuing with several papers by Lipton and Tarjan in 1979–1980. The size of the largest separator in a hierarchy of this type is closely related to the treewidth.

Moving forward to a time when the Robertson–Seymour ideas might have already started to float around, there is also a paper earlier than Graph Minors II that explicitly connects the pursuit-evasion and separation ideas, and that defines a notion of width equivalent to pathwidth: Ellis, J. A.; Sudborough, I. H.; Turner, J. S. (1983), "Graph separation and search number", Proc. 1983 Allerton Conf. on Communication, Control, and Computing.

Answer 4

In his monograph on graph theory, Reinhard Diestel traces the concept of treewidth and tree decompositions back to a 1976 paper by Halin (albeit not using these names). He also attributes to this paper the result that planar grid graphs have unbounded treewidth. Of course, he also mentions the later paper by Robertson and Seymour, who "rediscovered the concept, obviously unaware of Halin's work" (sorry if my translation is poor).

• Rudolf Halin. $S$-functions for graphs, J. Geometry 8 (1976):171–186
• Reinhard Diestel. Graphentheorie, 3rd German edition, Notizen zu Kapitel 10. (Some English edition of the book is available online for free download.)

Answer 5

The notion of tree-width [1] (and the similar notion branch-width) has been introduced by Robertson and Seymour in their seminal papers on Graph Minors.

They initially introduced tree-width in order to obtain a polynomial-time algorithm testing if a graph $G$ has a subgraph contractible to a fixed planar graph $H$.

See: N. Robertson, P.D. Seymour. Graph Minors. II. Algorithmic aspects of tree-width. JCT Series B (1986)