The Tutte Polynomial for Matroids of Bounded Branch-Width
Petr Hliněný · Combinatorics Probability Computing · 2006
It is a classical result of Jaeger, Vertigan and Welsh that evaluating the Tutte polynomial of a graph is #P-hard in all but a few special points. On the other hand, several papers in the past few years have shown that the Tutte polynomial of a graph can be efficiently computed for graphs of bounded tree-width. In this paper we present a recursive formula computing the Tutte polynomial of a matroid . This formula provides an algorithm computing the Tutte polynomial for a representable matroid of bounded branch-width in polynomial time with a fixed exponent.