Tutte polynomial

The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph formula_1 and contains information about how the graph is connected. It is denoted by formula_2.
The importance of this polynomial stems from the information it contains about formula_1. Though originally studied in algebraic graph theory as a generalization of counting problems related to graph coloring and nowhere-zero flow, it contains several famous other specializations from other sciences such as the Jones polynomial from knot theory and the partition functions of the Potts model from statistical physics. It is also the source of several central computational problems in theoretical computer science.
The Tutte polynomial has several equivalent definitions. It is equivalent to Whitney’s rank polynomial, Tutte’s own dichromatic polynomial and Fortuin–Kasteleyn’s random cluster model under simple transformations. It is essentially a generating function for the number of edge sets of a given size and connected components, with immediate generalizations to matroids. It is also the most general graph invariant that can be defined by a deletion–contraction recurrence. Several textbooks about graph theory and matroid theory devote entire chapters to it.
Definitions.
Definition. For an undirected graph formula_4 one may define the Tutte polynomial as
where formula_6 denotes the number of connected components of the graph formula_7. In this definition it is clear that formula_2 is well-defined and a polynomial in formula_9 and formula_10.
The same definition can be given using slightly different notation by letting formula_11 denote the rank of the graph formula_7. Then the Whitney rank generating function is defined as
Theorem (Tutte).
The connection to the Tutte polynomial is given by:
Reliability polynomial.
At formula_19, the Tutte polynomial specialises to the all-terminal reliability polynomial studied in network theory. For a connected graph "G" remove every edge with probability "p"; this models a network subject to random edge failures. Then the reliability polynomial is a function formula_20, a polynomial in "p", that gives the probability that every pair of vertices in "G" remains connected after the edges fail. The connection to the Tutte polynomial is given by
Dichromatic polynomial.
Tutte also defined a closer 2-variable generalization of the chromatic polynomial, the dichromatic polynomial of a graph. This is
where formula_6 is the number of connected components of the spanning subgraph ("V","A"). This is related to the corank-nullity polynomial by
The dichromatic polynomial does not generalize to matroids because "k"("A") is not a matroid property: different graphs with the same matroid can have different numbers of connected components.
Related polynomials.
Martin polynomial.
The Martin polynomial formula_25 of an oriented 4-regular graph formula_26 was defined by Pierre Martin in 1977. He showed that if "G" is a plane graph and formula_27 is its directed medial graph, then
Algorithms.
Deletion–contraction.
The deletion–contraction recurrence for the Tutte polynomial,
immediately yields a recursive algorithm for computing it for a given graph: as long as you can find an edge "e" that is not a loop or bridge, recursively compute the Tutte polynomial for when that edge is deleted, and when that edge is contracted. Then add the two sub-results together to get the overall Tutte polynomial for the graph.
The base case is a monomial formula_30 where "m" is the number of bridges, and "n" is the number of loops.
Within a polynomial factor, the running time "t" of this algorithm can be expressed in terms of the number of vertices "n" and the number of edges "m" of the graph,
a recurrence relation that scales as the Fibonacci numbers with solution
The analysis can be improved to within a polynomial factor of the number formula_33 of spanning trees of the input graph. For sparse graphs with formula_34 this running time is formula_35. For regular graphs of degree "k", the number of spanning trees can be bounded by
where
so the deletion–contraction algorithm runs within a polynomial factor of this bound. For example:
In practice, graph isomorphism testing is used to avoid some recursive calls. This approach works well for graphs that are quite sparse and exhibit many symmetries; the performance of the algorithm depends on the heuristic used to pick the edge "e".
Gaussian elimination.
In some restricted instances, the Tutte polynomial can be computed in polynomial time, ultimately because Gaussian elimination efficiently computes the matrix operations determinant and Pfaffian. These algorithms are themselves important results from algebraic graph theory and statistical mechanics.
formula_39 equals the number formula_33 of spanning trees of a connected graph. This is
computable in polynomial time as the determinant of a maximal principal submatrix of the Laplacian matrix of "G", an early result in algebraic graph theory known as Kirchhoff’s Matrix–Tree theorem. Likewise, the dimension of the bicycle space at formula_41 can be computed in polynomial time by Gaussian elimination.
For planar graphs, the partition function of the Ising model, i.e., the Tutte polynomial at the hyperbola formula_42, can be expressed as a Pfaffian and computed efficiently via the FKT algorithm. This idea was developed by Fisher, Kasteleyn, and 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 formula_42, 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
In particular, the output allows evaluating formula_46 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 Tutteformula_47 defined for every complex pair formula_47:
The hardness of these problems varies with the coordinates formula_47.
Exact computation.
If both "x" and "y" are non-negative integers, the problem formula_50 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 formula_47, one can define a rational analogue of #P.
The computational complexity of exactly computing formula_50 falls into one of two classes for any formula_55. The problem is #P-hard unless formula_47 lies on the hyperbola formula_57 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 formula_42 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 vertex degree at most three, save for the point formula_60, which counts nowhere-zero Z3-flows and is computable in polynomial time.
These results contain several notable special cases. For example, the problem of computing the partition function of the Ising model is #P-hard in general, even though celebrated algorithms of Onsager and Fisher solve it for planar lattices. Also, the Jones polynomial is #P-hard to compute. Finally, computing the number of four-colorings of a planar graph is #P-complete, even though the decision problem is trivial by the four color theorem. In contrast, it is easy to see that counting the number of three-colorings for planar graphs is #P-complete because the decision problem is known to be NP-complete via a parsimonious reduction.
Approximation.
The question which points admit a good approximation algorithm has been very well studied. Apart from the points that can be computed exactly in polynomial time, the only approximation algorithm known for formula_50 is Jerrum and Sinclair’s FPRAS, which works for points on the “Ising” hyperbola formula_42 for "y" > 0. If the input graphs are restricted to dense instances, with degree formula_63, there is an FPRAS if "x" ≥ 1, "y" ≥ 1.
Even though the situation is not as well understood as for exact computation, large areas of the plane are known to be hard to approximate.