Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width

S. D. NOBLE

doi:10.1017/S0963548398003551

Abstract

It is known that evaluating the Tutte polynomial, T(G; x, y), of a graph, G, is #P-hard at all but eight specific points and one specific curve of the (x, y)-plane. In contrast we show that if k is a fixed constant then for graphs of tree-width at most k there is an algorithm that will evaluate the polynomial at any point using only a linear number of multiplications and additions.

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Merino, C. and Welsh, D. J. A. 1999. Forests, colorings and acyclic orientations of the square lattice. Annals of Combinatorics, Vol. 3, Issue. 2-4, p. 417.

Welsh, D. J. A. and Merino, C. 2000. The Potts model and the Tutte polynomial. Journal of Mathematical Physics, Vol. 41, Issue. 3, p. 1127.

Welsh, Dominic and Gale, Amy 2001. Aspects of Complexity. p. 115.

McCartin, Catherine 2002. Mathematical Foundations of Computer Science 2002. Vol. 2420, Issue. , p. 556.

Makowsky, J.A. and Mariño, J.P. 2003. Farrell polynomials on graphs of bounded tree width. Advances in Applied Mathematics, Vol. 30, Issue. 1-2, p. 160.

Lotz, Martin and Makowsky, Johann A. 2004. On the algebraic complexity of some families of coloured Tutte polynomials. Advances in Applied Mathematics, Vol. 32, Issue. 1-2, p. 327.

Makowsky, J.A. 2004. Algorithmic uses of the Feferman–Vaught Theorem. Annals of Pure and Applied Logic, Vol. 126, Issue. 1-3, p. 159.

Makowsky, J.A. 2005. Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Applied Mathematics, Vol. 145, Issue. 2, p. 276.

Giménez, Omer Hliněný, Petr and Noy, Marc 2005. Graph-Theoretic Concepts in Computer Science. Vol. 3787, Issue. , p. 59.

Makowsky, J. A. Rotics, Udi Averbouch, Ilya and Godlin, Benny 2006. Graph-Theoretic Concepts in Computer Science. Vol. 4271, Issue. , p. 191.

Giménez, Omer Hliněný, Petr and Noy, Marc 2006. Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width. SIAM Journal on Discrete Mathematics, Vol. 20, Issue. 4, p. 932.

Makowsky, J. A. 2006. Logical Approaches to Computational Barriers. Vol. 3988, Issue. , p. 330.

Traldi, Lorenzo 2006. On the colored Tutte polynomial of a graph of bounded treewidth. Discrete Applied Mathematics, Vol. 154, Issue. 6, p. 1032.

McCartin, Catherine 2006. Parameterized counting problems. Annals of Pure and Applied Logic, Vol. 138, Issue. 1-3, p. 147.

Sharp, Alexa 2007. Algorithms – ESA 2007. Vol. 4698, Issue. , p. 510.

ELLIS-MONAGHAN, JOANNA A. and SARMIENTO, IRASEMA 2007. Distance Hereditary Graphs and the Interlace Polynomial. Combinatorics, Probability and Computing, Vol. 16, Issue. 6, p. 947.

Björklund, Andreas Husfeldt, Thore Kaski, Petteri and Koivisto, Mikko 2008. Computing the Tutte Polynomial in Vertex-Exponential Time. p. 677.

Makowsky, J. A. 2008. From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials. Theory of Computing Systems, Vol. 43, Issue. 3-4, p. 542.

Fischer, E. Makowsky, J.A. and Ravve, E.V. 2008. Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Applied Mathematics, Vol. 156, Issue. 4, p. 511.

Bläser, Markus and Hoffmann, Christian 2009. Algorithms - ESA 2009. Vol. 5757, Issue. , p. 623.

Download full list

Article contents

Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width

Abstract

Access options

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Article contents

Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width

Abstract

Access options

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests