Inapproximability of the Tutte polynomial

Alon, 1995, Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: the dense case, Random Struct. Algorithms, 6, 459, 10.1002/rsa.3240060409

Brylawski, 1982, The Tutte polynomial. I. General theory, 125

Dahlhaus, 1994, The complexity of multiterminal cuts, SIAM J. Comput., 23, 864, 10.1137/S0097539792225297

Dyer, 2004, The relative complexity of approximate counting problems, Algorithmica, 38, 471, 10.1007/s00453-003-1073-y

Dyer, 2000, The complexity of counting graph homomorphisms, Random Struct. Algorithms, 17, 260, 10.1002/1098-2418(200010/12)17:3/4<260::AID-RSA5>3.0.CO;2-W

Fisher, 1966, On the dimer solution of planar Ising models, J. Math. Phys., 7, 1776, 10.1063/1.1704825

Frederickson, 1981, Approximation algorithms for several graph augmentation problems, SIAM J. Comput., 10, 270, 10.1137/0210019

M.R. Garey, D.S. Johnson, Computers and intractability. W.H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences.

L.A. Goldberg, M. Jerrum, Inapproximability of the Tutte polynomial, in: STOC’07: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, ACM Press, New York, NY, USA, 2007, pp. 459–468.

Jaeger, 1990, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc., 108, 35, 10.1017/S0305004100068936

M. Jerrum, Counting, sampling and integration: algorithms and complexity, Birkhauser Boston, also see author’s website, 2003.

Jerrum, 1993, Polynomial-time approximation algorithms for the Ising model, SIAM J. Comput., 22, 1087, 10.1137/0222066

Jerrum, 1986, Random generation of combinatorial structures from a uniform distribution, Theor. Comput. Sci., 43, 169, 10.1016/0304-3975(86)90174-X

Karger, 2001, A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem, SIAM Rev., 43, 499, 10.1137/S0036144501387141

Linial, 1986, Hard enumeration problems in geometry and combinatorics, SIAM J. Algebraic Discrete Methods, 7, 331, 10.1137/0607036

Seymour, 1981, Nowhere-zero 6-flows, J. Combin. Theory B, 30, 130, 10.1016/0095-8956(81)90058-7

Sokal, 2005, The multivariate

L. Stockmeyer, The complexity of approximate counting, in: STOC’83: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, ACM Press, New York, NY, USA, 1983, pp. 118–126.

Tutte, 1954, A contribution to the theory of chromatic polynomials, Can. J. Math., 6, 80, 10.4153/CJM-1954-010-9

W.T. Tutte, Graph theory, Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, vol. 21, 1984. With a foreword by C. St. J.A. Nash-Williams.

Valiant, 1986, NP is as easy as detecting unique solutions, Theor. Comput. Sci., 47, 85, 10.1016/0304-3975(86)90135-0

D.J.A. Welsh, Complexity: Knots, Colourings and Counting, London Mathematical Society Lecture Note Series, vol. 186, Cambridge University Press, Cambridge, 1993.

Welsh, 1994, Randomised approximation in the Tutte plane, Combin. Probab. Comput., 3, 137, 10.1017/S0963548300001036

Zuckerman, 1996, On unapproximable versions of NP-complete problems, SIAM J. Comput., 25, 1293, 10.1137/S0097539794266407