A new edge selection heuristic for computing the Tutte polynomial of an undirected graph

Understand

We present a new edge selection heuristic and vertex ordering heuristic that together enable one to compute the Tutte polynomial of much larger sparse graphs than was previously doable.

• As a specific example, we are able to compute the Tutte polynomial of the truncated icosahedron graph using our Maple implementation in under 4 minutes on a single CPU.
• This compares with a recent result of Haggard, Pearce and Royle whose special purpose C++ software took one week on 150 computers.