Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T13:27:44.380Z Has data issue: false hasContentIssue false
  • English
  • Français

The Computational Complexity of the Tutte Plane: the Bipartite Case

Published online by Cambridge University Press:  12 September 2008

D. L. Vertigan  and
D. J. A. Welsh
D. L. Vertigan
Affiliation:
Mathematical Institute, University of Oxford, 24–29 St Giles, Oxford OX1 3LB
D. J. A. Welsh
Affiliation:
Merton College, University of Oxford, Oxford OX1 4JD and University of Bonn
Get access Rights & Permissions [Opens in a new window]

Abstract

Along different curves and at different points of the (x, y)-plane the Tutte polynomial evaluates a wide range of quantities. Some of these, such as the number of spanning trees of a graph and the partition function of the planar Ising model, can be computed in polynomial time, others are # P-hard. Here we give a complete characterisation of which points and curves are easy/hard in the bipartite case.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 2 , June 1992 , pp. 181 - 187
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Brylawski, T. H. (1980) The Tutte polynomial, Matroid theory and its applications. Centro Internazionale Matematico Evisto 3 Liguori, Naples, 125–275.Google Scholar
[2]Edwards, K. J. (to appear) The complexity of some graph colouring problems. Discrete Appl. Math.Google Scholar
[3]Jaeger, F., Vertigan, D. L. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Phil. Soc. 108, 35–53.CrossRefGoogle Scholar
[4]Linial, N. (1986) Hard enumeration problems in geometry and combinatorics. SIAM J. Alg. Disc. Math. 7, 331–335.CrossRefGoogle Scholar
[5]Lovász, L. and Plummer, M. D. (1986) Matching Theory. Akadémiai Kiadó, Budapest.Google Scholar
[6]Valiant, L. G. (1979) The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 410–421.CrossRefGoogle Scholar
[7]Vertigan, D. L. (submitted) The computational complexity of Tutte invariants for planar graphs. SIAM J. Comput.Google Scholar
[8]Vertigan, D. L. (submitted) Bicycle dimension and special points of the Tutte polynomial. J. Comb. Th. B.Google Scholar
[9]Welsh, D. J. A. (1976) Matroid Theory. London Math. Soc. Monograph 8. Academic Press, London.Google Scholar
[10]Welsh, D. J. A. (1990) The computational complexity of some classical problems from statistical physics. Disorder in Physical Systems. Oxford Univ. Press, 307–323.Google Scholar