The Tutte polynomial of a graph G is a widely-studied and very useful graph invariant. It’s a polynomial in two variables x, y that extends, among other things, the chromatic and flow polynomials of a graph. In a certain (well-defined) sense, it’s actually the most general object that obeys what’s called the deletion-contraction recurrence, which I’ll talk about in a bit. One particular specialization of the Tutte polynomial of interest is its value at x = 1, y = 0. This has at least two useful combinatorial interpretations; it counts the number of acyclic orientations of the edges of G with a fixed unique source, or, equivalently, it counts what are called the “maximal parking functions” of G. As it happens, this second interpretation is the one I’m most interested in, but the first is more useful for this discussion, so we’ll only consider it here. Throughout this post, we’ll let M(G) = T_G(1,0) be the Tutte polynomial evaluated at (1, 0).

**An explanation
**

I’m interested in computing M(G) as efficiently as possible for sparse graphs G. Note that the Tutte polynomial itself is NP-hard to compute, since (in particular) T_G(-2, 0) counts the 3-colorings of G, which is #P-hard. In fact, it’s known that computing the Tutte polynomial at almost any point is #P-hard in general — including, unfortunately, at (1, 0). However, there are some encouraging properties of M(G) that make me believe that, at least for certain families of graphs, it may be tractable if not strictly polynomial-time computable.

In this post, I’ll discuss some of the elementary properties of the recurrence relation defining M(G). I’ll follow up with a second post sometime in the next day or so, in which I’ll talk about the computational implications of these properties, and a third post (likely early next week) in which I plan to discuss heuristics for computing M(G).

**Deletion and Contraction**

Okay, so in order to talk about the Tutte polynomial, I have to talk about the deletion-contraction recurrence. This is the following recurrence relation:

f(G) = f(G/e) + f(G – e) (1)

where G is a graph, e is a non-loop, non-bridge edge, G – e is the graph obtained by removing edge e from G, and G/e is the edge contraction of G at e. We can take f to be the Tutte polynomial T_G(x, y), and then T_G obeys (1). In addition, any restriction or evaluation of T_G will also obey the recurrence. This is the starting point for computing M(G).

**The base cases**

Of course, a recursive formula is useless without easy-to-compute base cases. Fortunately, these are quite simple to compute for M(G), and are as follows:

M(G) = 1 if G is a tree

M(G) = 0 if G contains a loop

The proof is simple: considering M(G) as the number of acyclic orientations of G with a fixed unique source, it is clear that if G contains a loop, M(G) = 0. Now let G be a tree rooted at v. It is clear that there is exactly one acyclic orientation with v as its unique source; every non-leaf node must have out-edges to exactly its children.

**Special Properties**

M(G) has several other properties which are useful in working with the deletion-contraction recurrence. First, suppose that G is a multigraph without loops. Consider the simple graph G’ obtained by replacing multiple copies of an edge of G with a single edge; then M(G) = M(G’).

Now suppose that G has a vertex of degree 1. Let G’ be the graph obtained from G by removing that vertex and its incident edge; then M(G) = M(G’) again. Extending, if G contains a bridge connecting to a tree, we can remove that tree and the bridge from G without changing the value of M. (The proofs of these statements are left to the reader.)

Finally, we note that depending on the combinatorial interpretation of M(G), there are several straightforward bijections between the set corresponding to M(G) and the union of the sets corresponding to M(G/e) and to M(G-e). While this is unlikely to play a role in the computational discussion, it is a useful fact to have around.

Part II will be up in the next day or two, depending on when I have time to write it. Any questions or properties of M(G) I overlooked are welcome in the comments!

Tags: graph theory, parking function, research, spanning tree, Tutte polynomial

July 16, 2009 at 03:58 |

[…] my research project on counting acyclic orientations has been moving along, but I don’t quite feel comfortable (yet) posting my progress on this […]

May 31, 2010 at 16:32 |

You have done it once again. Great read.