The Tutte Polynomial for Matroids of Bounded Branch-Width
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | Combin. Prob. Computing |
| MU Faculty or unit | |
| Citation | |
| Web | |
| Field | General mathematics |
| Keywords | representable matroid; Tutte polynomial; branch-width; |
| Description | It is a classical result of Jaeger, Vertigan and Welsh that evaluating the Tutte polynomial of a graph is $\#P$-hard in all but few special points. On the other hand, several papers in past 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 $\md M$ represented over a finite field (which includes all graphic matroids), using a so called parse tree of a branch-decomposition of $\md M$. This formula provides an algorithm computing the Tutte polynomial for a representable matroid of bounded branch-width in polynomial time with a fixed exponent. |
| Related projects: |