This article is about the Tutte polynomial of a graph. For the Tutte polynomial of a matroid, see
Matroid.
The polynomial is the Tutte polynomial of the
bull graph. The red line shows the intersection with the plane , which is essentially equivalent to the chromatic 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 and contains information about how the graph is connected. It is denoted by .
The Tutte polynomial has several equivalent definitions. It is essentially 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.[1][2][3]
Definitions
Definition. For an undirected graph one may define the Tutte polynomial as
where denotes the number of
connected components of the graph . In this definition it is clear that is well-defined and a polynomial in and .
The same definition can be given using slightly different notation by letting denote the
rank of the graph . Then the Whitney rank generating function is defined as
The two functions are equivalent under a simple change of variables:
Tutte’s dichromatic polynomial is the result of another simple transformation:
Tutte’s original definition of is equivalent but less easily stated. For connected we set
where denotes the number of
spanning trees of internal activity and external activity.
A third definition uses a deletion–contraction recurrence. The
edge contraction of graph is the graph obtained by merging the vertices and and removing the edge . We write for the graph where the edge is merely removed. Then the Tutte polynomial is defined by the recurrence relation
Especially, the chromatic polynomial of a planar graph is the flow polynomial of its dual. Tutte refers to such functions as V-functions.[6]
Examples
Isomorphic graphs have the same Tutte polynomial, but the converse is not true. For example, the Tutte polynomial of every tree on edges is .
Tutte polynomials are often given in tabular form by listing the coefficients of in row and column . For example, the Tutte polynomial of the
Petersen graph,
is given by the following table.
0
36
84
75
35
9
1
36
168
171
65
10
120
240
105
15
180
170
30
170
70
114
12
56
21
6
1
Other example, the Tutte polynomial of the octahedron graph is given by
History
W. T. Tutte’s interest in the
deletion–contraction formula started in his undergraduate days at
Trinity College, Cambridge, originally motivated by
perfect rectangles and
spanning trees. He often applied the formula in his research and “wondered if there were other interesting
functions of graphs, invariant under isomorphism, with similar recursion formulae.”[6]R. M. Foster had already observed that the
chromatic polynomial is one such function, and Tutte began to discover more. His original terminology for graph invariants that satisfy the deletion–contraction recursion was W-function, and V-function if multiplicative over components. Tutte writes, “Playing with my W-functions I obtained a two-variable polynomial from which either the chromatic polynomial or the flow-polynomial could be obtained by setting one of the variables equal to zero, and adjusting signs.”[6] Tutte called this function the dichromate, as he saw it as a generalization of the chromatic polynomial to two variables, but it is usually referred to as the Tutte polynomial. In Tutte’s words, “This may be unfair to
Hassler Whitney who knew and used analogous coefficients without bothering to affix them to two variables.” (There is “notable confusion”[7] about the terms dichromate and dichromatic polynomial, introduced by Tutte in different paper, and which differ only slightly.) The generalisation of the Tutte polynomial to matroids was first published by
Crapo, though it appears already in Tutte’s thesis.[8]
At various points and lines of the -plane, the Tutte polynomial evaluates to quantities that have been studied in their own right in diverse fields of mathematics and physics. Part of the appeal of the Tutte polynomial comes from the unifying framework it provides for analysing these quantities.
At , the Tutte polynomial specialises to the chromatic polynomial,
where denotes the number of connected components of G.
For integer λ the value of chromatic polynomial equals the number of
vertex colourings of G using a set of λ colours. It is clear that does not depend on the set of colours. What is less clear is that it is the evaluation at λ of a polynomial with integer coefficients. To see this, we observe:
If G has n vertices and no edges, then .
If G contains a loop (a single edge connecting a vertex to itself), then .
If e is an edge which is not a loop, then
The three conditions above enable us to calculate , by applying a sequence of edge deletions and contractions; but they give no guarantee that a different sequence of deletions and contractions will lead to the same value. The guarantee comes from the fact that counts something, independently of the recurrence. In particular,
Along the hyperbola , the Tutte polynomial of a planar graph specialises to the
Jones polynomial of an associated
alternating knot.
Individual points
(2,1)
counts the number of
forests, i.e., the number of acyclic edge subsets.
(1,1)
counts the number of spanning forests (edge subsets without cycles and the same number of connected components as G). If the graph is connected, counts the number of spanning trees.
(1,2)
counts the number of spanning subgraphs (edge subsets with the same number of connected components as G).
is the number where is the number of edges of graph G.
(0,−2)
If G is a 4-regular graph, then
counts the number of
Eulerian orientations of G. Here is the number of connected components of G.[10]
(3,3)
If G is the m × ngrid graph, then counts the number of ways to tile a rectangle of width 4m and height 4n with
T-tetrominoes.[12][13]
If G is a
planar graph, then equals the sum over weighted Eulerian orientations in a
medial graph of G, where the weight of an orientation is 2 to the number of saddle vertices of the orientation (that is, the number of vertices with incident edges cyclicly ordered "in, out, in out").[14]
The partition functions for the Ising model and the 3- and 4-state Potts models drawn in the Tutte plane.
Define the hyperbola in the xy−plane:
the Tutte polynomial specialises to the partition function, of the
Ising model studied in
statistical physics. Specifically, along the hyperbola the two are related by the equation:[15]
In particular,
for all complex α.
More generally, if for any positive integer q, we define the hyperbola:
then the Tutte polynomial specialises to the partition function of the q-state
Potts model. Various physical quantities analysed in the framework of the Potts model translate to specific parts of the .
Correspondences between the Potts model and the Tutte plane [16]
At , the Tutte polynomial specialises to the flow polynomial studied in combinatorics. For a connected and undirected graph G and integer k, a nowhere-zero k-flow is an assignment of “flow” values to the edges of an arbitrary orientation of G such that the total flow entering and leaving each vertex is congruent modulo k. The flow polynomial denotes the number of nowhere-zero k-flows. This value is intimately connected with the chromatic polynomial, in fact, if G is a
planar graph, the chromatic polynomial of G is equivalent to the flow polynomial of its
dual graph in the sense that
Theorem (Tutte).
The connection to the Tutte polynomial is given by:
The reliability polynomial drawn in the Tutte plane
At , 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 , 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 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 of an oriented 4-regular graph was defined by Pierre Martin in 1977.[17] He showed that if G is a plane graph and is its
directed medial graph, then
The deletion–contraction algorithm applied to the
diamond graph. Red edges are deleted in the left child and contracted in the right child. The resulting polynomial is the sum of the monomials at the leaves, . Based on
Welsh & Merino (2000).
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 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,
The analysis can be improved to within a polynomial factor of the number of
spanning trees of the input graph.[19] For
sparse graphs with this running time is . 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:[20]
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.[19][21][22]
equals the number 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 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 , 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 , 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[23] 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
The Tutte plane. Every point in the real plane corresponds to a computational problem . At any red point, the problem is polynomial-time computable; at any blue point, the problem is #P-hard in general, but polynomial-time computable for planar graphs; and at any point in the white regions, the problem is #P-hard even for bipartite planar graphs.
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.[24]
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.[25] 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.[26] 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 , which counts nowhere-zero Z3-flows and is computable in polynomial time.[27]
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 is Jerrum and Sinclair’s FPRAS, which works for points on the “Ising” hyperbola for y > 0. If the input graphs are restricted to dense instances, with degree , there is an FPRAS if x ≥ 1, y ≥ 1.[28]
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.[24]
Alon, N.; Frieze, A.;
Welsh, D. J. A. (1995), "Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case", Random Structures and Algorithms, 6 (4): 459–478,
doi:
10.1002/rsa.3240060409.
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), "Computing the Tutte polynomial in vertex-exponential time", Proc. of the 47th annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pp. 677–686,
arXiv:0711.2585,
doi:
10.1109/FOCS.2008.40,
ISBN978-0-7695-3436-7.
Farr, Graham E. (2007), "Tutte-Whitney polynomials: some history and generalizations", in
Grimmett, Geoffrey; McDiarmid, Colin (eds.), Combinatorics, complexity, and chance. A tribute to Dominic Welsh, Oxford Lecture Series in Mathematics and its Applications, vol. 34,
Oxford University Press, pp. 28–52,
ISBN978-0-19-857127-8,
Zbl1124.05020.
Sokal, Alan D. (2005), "The multivariate Tutte polynomial (alias Potts model) for graphs and matroids", in Webb, Bridget S. (ed.), Surveys in Combinatorics, London Mathematical Society Lecture Note Series, vol. 327,
Cambridge University Press, pp. 173–226,
arXiv:math/0503607,
doi:
10.1017/CBO9780511734885.009.