Edge-Selection Heuristics for Computing Tutte Polynomials
Author(s). David J. Pearce, Gary Haggard and Gordon Royle.
Venue. In Chicago Journal of Theoretical Computer Science, 2010 (6), 2010.
Abstract. The Tutte polynomial of a graph, also known as the partition function of theq-statePotts model, is a 2-variable polynomial graph invariant of considerable importance in bothcombinatorics and statistical physics. It contains several other polynomial invariants, such asthe chromatic polynomial and flow polynomial as partial evaluations, and various numericalinvariants such as the number of spanning trees as complete evaluations. We have developedthe most efficient algorithm to-date for computing the Tutte polynomial of a graph. Animportant component of the algorithm affecting efficiency is the choice of edge to work onat each stage in the computation. In this paper, we present and discuss two edge-selectionheuristics which (respectively) give good performance on sparse and dense graphs. We alsopresent experimental data comparing these heuristics against a range of others to demonstratetheir effectiveness.