Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-29T18:21:46.875Z Has data issue: false hasContentIssue false
  • English
  • Français

On the computational complexity of the Jones and Tutte polynomials

Published online by Cambridge University Press:  24 October 2008

F. Jaeger ,
D. L. Vertigan  and
D. J. A. Welsh
F. Jaeger
Affiliation:
Laboratoire de Structures Discrètes, Institut IMAG, Grenoble, France
D. L. Vertigan
Affiliation:
Merton College and the Mathematical Institute, University of Oxford
D. J. A. Welsh
Affiliation:
Merton College and the Mathematical Institute, University of Oxford
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that determining the Jones polynomial of an alternating link is #P-hard. This is a special case of a wide range of results on the general intractability of the evaluation of the Tutte polynomial T(M; x, y) of a matroid M except for a few listed special points and curves of the (x, y)-plane. In particular the problem of evaluating the Tutte polynomial of a graph at a point in the (x, y)-plane is #P-hard except when (x − 1)(y − 1) = 1 or when (x, y) equals (1, 1), (−1, −1), (0, −1), (−1, 0), (i, −i), (−i, i), (j, j2), (j2, j) where j = e2πi/3

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 108 , Issue 1 , July 1990 , pp. 35 - 53
Copyright
Copyright © Cambridge Philosophical Society 1990

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

REFERENCES

[1]Baxter, R. J.. Exactly Solved Models in Statistical Mechanics (Academic Press, 1982).Google Scholar
[2]Berman, L. and Hartmanis, J.. On isomorphisms and density of NP and other complete sets. SIAM J. Comput. 6 (1977), 305–321.CrossRefGoogle Scholar
[3]Bondy, J. A. and Murty, U. S. R.. Graph Theory with Applications (American Elsevier and Macmillan, 1976).CrossRefGoogle Scholar
[4]Brylawski, T. H.. A decomposition for combinatorial geometries. Trans. Amer. Math. Soc. 171 (1972), 235–282.CrossRefGoogle Scholar
[5]Brylawski, T. H. and Lucas, D.. Uniquely representable combinatorial geometries. In Proceedings of International Colloquium in Combinatorial Theory, Rome, Italy, 1973; Atti Convegni Lincei 17 (1976), 83–104.Google Scholar
[6]Brylawski, T. H.. The Tutte polynomial; matroid theory and its applications. Centro Internazionale Matematico Estivo 3 (1980), 125–275.Google Scholar
[7]Brylawski, T. H. and Oxley, J. G.. The Tutte polynomial and its applications. In Matroid Theory, vol. 3 (ed. White, N.) (Cambridge University Press, to appear).Google Scholar
[8]Crapo, H.. The Tutte polynomial. Aequationes Math. 3 (1969), 211–229.CrossRefGoogle Scholar
[9]Fisher, M. E.. On the dimer solution of planar Ising models. J. Math. Phys. 7 (1966), 1776–1781.CrossRefGoogle Scholar
[10]Garey, M. R. and Johnson, D. S.. Computers and Intractability – A Guide to the Theory of NP-completeness (Freeman, 1979).Google Scholar
[11]Garey, M. R., Johnson, D. S. and Stockmeyer, L.. Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1 (1976), 237–267.CrossRefGoogle Scholar
[12]Greene, C.. Weight enumeration and the geometry of linear codes. Stud. Appl. Math. 99 (1976), 117–128.Google Scholar
[13]Grötschel, M., Lovász, L. and Schrijver, A.. Geometric Algorithms and Combinatorial Optimization (Springer-Verlag, 1988).CrossRefGoogle Scholar
[14]Jaeger, F.. On Tutte polynomials and cycles of plane graphs. J. Combin. Theory Ser. B 44 (1988), 129–146.CrossRefGoogle Scholar
[15]Jaeger, F.. On Tutte polynomials and link polynomials. Proc. Amer. Math. Soc. 103 (1988), 647–654.CrossRefGoogle Scholar
[16]Jaeger, F.. On Tutte polynomials and bicycle dimension of ternary matroids. Proc. Amer. Math. Soc. 107 (1989), 17–25.CrossRefGoogle Scholar
[17]Jaeger, F.. Nowhere zero flow problems. In Selected Topics in Graph Theory 3 (ed. Beineke, L. and Wilson, R. J.) (Academic Press, 1988), pp. 71–95.Google Scholar
[18]Jerrum, M. R.. The complexity of evaluating multivariate polynomials. Ph.D. thesis, University of Edinburgh (1981).Google Scholar
[19]Jerrum, M. R.. 2-dimensional monomer-dimer systems are computationally intractable. J. Statist. Phys. 48 (1987), 121–134.CrossRefGoogle Scholar
[20]Jerrum, M.. (Private communication, March 1989.)Google Scholar
[21]Jones, V. F. R.. A polynomial invariant for knots via Von Neumann algebras. Bull. Amer. Math. Soc. 12 (1985), 103–111.CrossRefGoogle Scholar
[22]Kasteleyn, P. W.. Graph theory and crystal physics. In Graph Theory and Theoretical Physics (ed. Harary, F.) (Academic Press, 1967), pp. 43–110.Google Scholar
[23]Kauffman, L.. On Knots (Princeton University Press, 1987).Google Scholar
[24]Vergnas, M. Las. Convexity in oriented matroids. J. Combin. Theory Ser. B 29 (1980), 231–243.CrossRefGoogle Scholar
Vergnas, M. LasMatroides orientables. C. R. Acad. Sci. Paris Ser. A 280 (1975), 61–64.Google Scholar
[25]Vergnas, M. Las. Le polynôme de Martin d'un graphe Eulérien. Ann. Discrete Math. 17 (1983), 397–411.Google Scholar
[26]Lickorish, W. B. R.. Polynomials for links. Bull. London Math. Soc. 20 (1988), 558–588.CrossRefGoogle Scholar
[27]Linial, N.. Hard enumeration problems in geometry and combinatorics. SIAM J. Algebraic Discrete Methods 7 (1986), 331–335.CrossRefGoogle Scholar
[28]Lipson, A. S.. An evaluation of a link polynomial. Math. Proc. Cambridge Philos. Soc. 100 (1986), 361–364.CrossRefGoogle Scholar
[29]MacWilliams, F. J. and Sloane, N. J. A.. The Theory of Error Correcting Codes (North Holland, 1977).Google Scholar
[30]Martin, P.. Remarkable valuation of the dichromatic polynomial of planar multigraphs. J. Combin. Theory Ser. B 24 (1978), 318–324.CrossRefGoogle Scholar
[31]Oxley, J. G. and Welsh, D. J. A.. The Tutte polynomial and percolation. In Graph Theory and Related Topics (Academic Press, 1979), pp. 329–339.Google Scholar
[32]Provan, J. S.. The complexity of reliability computations in planar and acyclic graphs. SIAM J. Comput. 15 (1986), 694–702.CrossRefGoogle Scholar
[33]Provan, J. S. and Ball, M. O.. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12 (1983), 777–788.CrossRefGoogle Scholar
[34]Robinson, G. C. and Welsh, D. J. A.. The computational complexity of matroid properties. Math. Proc. Cambridge Philos. Soc. 87 (1980), 29–45.CrossRefGoogle Scholar
[35]Rosenstiehl, P. and Read, R. C.. On the principal edge tripartition of a graph. Ann. Discrete Math. 3 (1978), 195–226.CrossRefGoogle Scholar
[36]Seymour, P. D.. Decomposition of regular matroids. J. Combin. Theory Ser. B 28 (1980), 305–359.CrossRefGoogle Scholar
[37]Seymour, P. D.. Nowhere-zero 6-flows. J. Combin. Theory Ser. B 30 (1981), 130–135.CrossRefGoogle Scholar
[38]Stanley, R. P.. Enumerative Combinatorics, vol. 1 (Wadsworth & Brooks/Cole, 1986).CrossRefGoogle Scholar
[39]Thistlethwaite, M. B.. A spanning tree expansion of the Jones polynomial. Topology 26 (1987), 297–309.CrossRefGoogle Scholar
[40]Thistlethwaite, M. B.. On the Kauffman polynomial of an adequate link. Invent. Math. 93 (1988), 285–296.CrossRefGoogle Scholar
[41]Tutte, W. T.. A ring in graph theory. Proc. Cambridge Philos. Soc. 43 (1947), 26–40.CrossRefGoogle Scholar
[42]Valiant, L. G.. The complexity of computing the permanent. Theoret. Comput. Sci. 8 (1979), 189–201.CrossRefGoogle Scholar
[43]Valiant, L. G.. The complexity of enumeration and reliability problems. SIAM J. Comput. 8 (1979), 410–421.CrossRefGoogle Scholar
[44]Vertigan, D. L.. On the computational complexity of Tutte, Homfly and Kauffman invariants (to appear).Google Scholar
[45]Welsh, D. J. A.. Matroid Theory. London Math. Soc. Monograph no. 8 (Academic Press, 1976).Google Scholar
[46]Welsh, D. J. A.. Matroids and their applications. In Selected Topics in Oraph Theory 3 (ed. Beineke, L. and Wilson, R. J.) (Academic Press, 1988), pp. 43–71.Google Scholar
[47]Whitney, H.. A logical expansion in mathematics. Bull. Amer. Math. Soc. 38 (1932), 572–579.CrossRefGoogle Scholar
[48]Whitney, H.. On the abstract properties of linear dependence. Amer. J. Math. 57 (1935), 509–533.CrossRefGoogle Scholar
[49]Zaslavsky, T.. Facing up to arrangements: face count formulas for partitions of spaces by hyperplanes. Memoirs Amer. Math. Soc. vol. 154 (American Mathematical Society, 1975).Google Scholar