We described an algorithm to compute the Tutte polynomial in
- Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Computing the Tutte polynomial in vertex-exponential time. 9th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA. IEEE Computer Society 2008, pp. 677–686. [PDF]
In fact, we even have an implementation of this algorithm, which has been available on request from the authors for a while. We have now put this implementation on the public repository GitHub:
You can either download a tar archive from there, or (if you use Git) clone the repository.
The code uses some tricks to speed up the implementation. for example, the coefficients are computed modulo several small prime moduli and then assembled with the Chinese remainder theorem.
However, the code remains a very faithful implementation of the underlying inclusion–exclusion idea and uses no other algorithmic ideas. This is the fastest worst-case implementation known to us and outperforms other implementations (for example, on dense graphs) around n(G) = 16. However, for specific input graphs you might meet in the wild, for instance graphs with few edges, small cuts, or many symmetries, other algorithms could perform much better. A very good implementation of many of these other ideas by Gary Haggard, David J. Pearce and Gordon Royle, can be found at
The work in our implementation is done in a C program “tutte_bhkk”, which can be run from the command line. The input is given in 0/1 adjacency matrix format; more precisely, the input is “N row1 row2 ... rowN”, where N is the number of vertices and rowJ is the Jth row of the adjacency matrix. For example, a triangle is given as
3 0 1 1 1 0 1 1 1 0
The output is a table of coefficients, where the entry at row i, column j gives the coefficient of the monomial xiyj for i, j=0, 1, 2, … in
where G is the input graph, V is the vertex set of G, E is the edge set of G, c(G) is the number of connected components in G, cF(G) is the number of connected components in the subgraph of G with vertex set V and edge set F, and n(G) is the number of vertices in G.
For example, for the triangle we obtain the output
0 1
1
1
or equivalently, TG(x, y) = x + x2 + y.
The python module “tutte.py” is a very simple wrapper that serves two purposes.
First, it connects “tutte_bhkk” to the networkx library, which is a collection of graph algorithms and data structures for python. In particular, “tutte.py” exports the function tutte_poly(G), which returns the Tutte polynomial of a given networkx.Graph.
For example, you can write another python script like this:
from tutte import tutte_poly
from networkx import chvatal_graph
print tutte_poly(chvatal_graph())
Second, “tutte.py” can be called from the command line and serves as a convenient interface to “tutte_bhkk”. The input can be given either as an edge list on standard input, or in a compact shorthand format. The output is either a table of coefficients (default) or TeX.
Some examples:
$ python tutte.py --petersen
$ python tutte.py --short="0--1 1--2 2--0" --output=tex
$ python tutte.py
0 1
1 2
2 0
^D
Thore Husfeldt 