The computational complexity of knot and matroid polynomials. (English) Zbl 0816.57008
Summary: The computational complexity of the Tutte plane is surveyed. For example, except for a finite set of 9 points and two special curves, evaluating the Tutte polynomial is \(\#\)P-hard even for planar graphs. One of these special curves is the trivial hyperbola (\(x-1) (y-1)=1\), the other is where the Tutte polynomial specializes to the Ising partition function. Corresponding results for knot polynomials and other classes of matroids are given.
MSC:
| 57M25 | Knots and links in the \(3\)-sphere (MSC2010) |
| 57M15 | Relations of low-dimensional topology with graph theory |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C99 | Graph theory |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
References:
| [1] | Brylawski, T. H., A decomposition for combinatorial geometries, Trans. Amer. Math. Soc., 171, 235-282 (1972) · Zbl 0224.05007 |
| [2] | Brylawski, T. H., The Tutte polynomial, matroid theory and its applications, Centro Internazionale Matematico Estivo 3 Liguori, 125-275 (1980), Naples · Zbl 1302.05023 |
| [3] | T.H. Brylawski and J.G. Oxley, The Tutte polynomial and its applications, in: N. White, ed, Matroid Theory, Vol. 3 (Cambridge Univ. Press, Cambridge, to appear).; T.H. Brylawski and J.G. Oxley, The Tutte polynomial and its applications, in: N. White, ed, Matroid Theory, Vol. 3 (Cambridge Univ. Press, Cambridge, to appear). · Zbl 0769.05026 |
| [4] | Burde, G.; Zieschang, H., Knots (1985), de Gruyter: de Gruyter Berlin · Zbl 0568.57001 |
| [5] | Crapo, H., The Tutte polynomial, Aequationes Math., 3, 211-229 (1969) · Zbl 0197.50202 |
| [6] | Fisher, M. E., On the dimer solution of planar Ising models, J. Math. Phys., 7, 1776-1781 (1965) |
| [7] | Garey, M. R.; Johnson, D. S., Computers and Intractability — A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [8] | Garey, M. R.; Johnson, D. S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237-267 (1976) · Zbl 0338.05120 |
| [9] | Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization (1988), Springer: Springer Berlin · Zbl 0634.05001 |
| [10] | Haken, W., Theorie der Normalflächen, Acta Math., 105, 245-375 (1961) · Zbl 0100.19402 |
| [11] | Hemion, G., On the classification of homeomorphisms of 2-manifolds and the classification of 3-manifolds, Acta Math., 142, 123-155 (1979) · Zbl 0402.57027 |
| [12] | Jaeger, F., Nowhere zero flow problems, (Beineke, L.; Wilson, R. J., Selected Topics in Graph Theory, 3 (1988), Academic Press: Academic Press New York), 71-92 · Zbl 0658.05034 |
| [13] | Jaeger, F., On Tutte polynomials and link polynomials, Proc. Amer. Math. Soc., 103, 647-654 (1988) · Zbl 0665.57006 |
| [14] | F. Jaeger, On Tutte polynomials and bicycle dimension of ternary matroids, Proc. Amer. Math. Soc., to appear.; F. Jaeger, On Tutte polynomials and bicycle dimension of ternary matroids, Proc. Amer. Math. Soc., to appear. · Zbl 0669.05023 |
| [15] | Jaeger, F.; Vertigan, D. L.; Welsh, D. J.A., On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Camb. Phil. Soc., 108, 35-53 (1990) · Zbl 0747.57006 |
| [16] | Jones, V. F.R., A polynomial invariant for knots via Von Neumann algebras, Bull. Amer. Math. Soc., 12, 103-111 (1985) · Zbl 0564.57006 |
| [17] | Kasteleyn, P. W., Graph theory and crystal physics, (Harary, F., Graph Theory and Theoretical Physics (1967), Academic Press: Academic Press London), 43-110 · Zbl 0205.28402 |
| [18] | Kauffman, L. H., On Knots, (Ann. Math. Stud., 115 (1987), Princeton Univ. Press) · Zbl 0749.57002 |
| [19] | Kauffmann, L. H., State models and the Jones polynomial, Topology, 26, 395-407 (1987) · Zbl 0622.57004 |
| [20] | Korte, B.; Jensen, P., Complexity of matroid property algorithms, SIAM J. Comput., 11, 184-190 (1982) · Zbl 0478.68044 |
| [21] | Lickorish, W. B.R., Polynomials for links, Bull. Lond. Math. Soc., 20, 558-588 (1988) · Zbl 0685.57001 |
| [22] | Lickorish, W. B.R., The panorama of polynomials for knots, links and skeins, Contemp. Math., 78, 399-414 (1988) · Zbl 0703.57007 |
| [23] | Murasugi, K., Jones polynomials and classical conjectures in knot theory, Topology, 26, 187-194 (1987) · Zbl 0628.57004 |
| [24] | Oxley, J. G.; Welsh, D. J.A., The Tutte polynomial and percolation, (Bondy, J. A.; Murty, U. S.R., Graph Theory and Related Topics (1979), Academic Press: Academic Press London), 329-339 · Zbl 0498.05018 |
| [25] | Oxley, J. G.; Welsh, D. J.A., Tutte polynomials computable in polynomial time, Discrete Math., 109, 185-192 (1992) · Zbl 0780.05011 |
| [26] | Robinson, G. C.; Welsh, D. J.A., The computational complexity of matroid properties, Math. Proc. Camb. Phil. Soc., 87, 29-45 (1980) · Zbl 0434.68030 |
| [27] | Tait, P. G., On Knots I, II, III, (Scientific Papers, Vol. I (1898), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 273-347 · JFM 29.0021.04 |
| [28] | Thistlethwaite, M. B., A spanning tree expansion of the Jones polynomial, Topology, 26, 297-309 (1987) · Zbl 0622.57003 |
| [29] | Thistlethwaite, M. B., On the Kauffman polynomial of an adequate link, Invent. Math., 93, 285-296 (1988) · Zbl 0645.57007 |
| [30] | Tutte, W. T., A ring in graph theory, Proc. Camb. Phil. Soc., 43, 26-40 (1947) · Zbl 0031.41803 |
| [31] | Valiant, L. G., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 410-421 (1979) · Zbl 0419.68082 |
| [32] | D.L. Vertigan, The computational complexity of Tutte invariants for planar graphs, SIAM. J. Comput., submitted.; D.L. Vertigan, The computational complexity of Tutte invariants for planar graphs, SIAM. J. Comput., submitted. · Zbl 1089.05017 |
| [33] | D.L. Vertigan, The computational complexity of Homfly and Kauffman invariants, to appear.; D.L. Vertigan, The computational complexity of Homfly and Kauffman invariants, to appear. · Zbl 1089.05017 |
| [34] | Waldhausen, F., Recent results on sufficiently large 3-manifolds, Proc. Symp. Pure Math. Amer. Math. Soc., 32, 21-38 (1978) · Zbl 0391.57011 |
| [35] | Welsh, D. J.A., Matroid Theory, (London Math. Soc. Monograph, 8 (1976), Academic Press: Academic Press London) · Zbl 0343.05002 |
| [36] | Welsh, D. J.A., The computational complexity of some classical problems from statistical physics, (Grimmett, G. R.; Welsh, D. J.A., Disorder in Physical Systems (1990), Oxford Univ. Press: Oxford Univ. Press Oxford), 307-321 · Zbl 0737.60094 |
| [37] | Welsh, D. J.A., The complexity of knots, Ann. Discrete Math., 55, 159-172 (1993) · Zbl 0799.68008 |
| [38] | Whitney, H., A logical expansion in mathematics, Bull. Amer. Math. Soc., 38, 572-579 (1932) · JFM 58.0605.08 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
