Computing Tutte Polynomials
Author(s). Gary Haggard, David J. Pearce and Gordon Royle.
Venue. In ACM Transactions on Mathematical Software, 37 (3), pages article 24, 2010. ©ACM Press
Abstract: The Tutte polynomial of a graph is a 2-variable polynomial graph invariant of considerable importance in both combinatorics and statistical physics. It contains several other polynomial invariants, such as the chromatic polynomial and flow polynomial as partial evaluations, and various numerical invariants such as the number of spanning trees as complete evaluations. However, despite its ubiquity, there are no widely-available effective computational tools able to compute the Tutte polynomial of a general graph of reasonable size. In this paper we describe the implementation of an algorithm that exploits isomorphisms in the computation tree to extend the range of graphs for which it is feasible to compute their Tutte polynomials, and we demonstrate the utility of the program by finding counterexamples to a conjecture of Welsh on the location of the real flow roots of a graph.
Notes. The latest version of my C++ implementation is available here and also on GitHub. A Java implementation is maintained separately here. Finally, the algorithm has also been incorporated into both Mathematica and Sage.