Temperley to compute the number of dimer covers of a planar lattice model. Markov chain Monte Carlo Using a Markov chain Monte Carlo method, the Tutte polynomial can be arbitrarily well approximated along the positive branch of , equivalently, the partition function of the ferromagnetic Ising model. This exploits the close connection between the Ising model and the problem of counting matchings in a graph. The idea behind this celebrated result of Jerrum and Sinclair is to set up a Markov chain whose states are the matchings of the input graph. The transitions are defined by choosing edges at random and modifying the matching accordingly. The resulting Markov chain is rapidly mixing and leads to “sufficiently random” matchings, which can be used to recover the partition function using random sampling. The resulting algorithm is a fully polynomial-time randomized approximation scheme (fpras). Computational complexity Several computational problems are associated with the Tutte polynomial. The most straightforward one is Input: A graph Output: The coefficients of In particular, the output allows evaluating which is equivalent to counting the number of 3-colourings of G. This latter question is #P-complete, even when restricted to the family of planar graphs, so the problem of computing the coefficients of the Tutte polynomial for a given graph is #P-hard even for planar graphs. Much more attention has been given to the family of problems called Tutte defined for every complex pair : Input: A graph Output: The value of The hardness of these problems varies with the coordinates . Exact computation If both x and y are non-negative integers, the problem belongs to #P. For general integer pairs, the Tutte polynomial contains negative terms, which places the problem in the complexity class GapP, the closure of #P under subtraction. To accommodate rational coordinates , one can define a rational analogue of #P. The computational complexity of exactly computing falls into one of two classes for any . The problem is #P-hard unless lies on the hyperbola or is one of the points in which cases it is computable in polynomial time. If the problem is restricted to the class of planar graphs, the points on the hyperbola become polynomial-time computable as well. All other points remain #P-hard, even for bipartite planar graphs. In his paper on the dichotomy for planar graphs, Vertigan claims (in his conclusion) that the same result holds when further restricted to graphs with