Tutte polynomial
   HOME

TheInfoList



OR:

The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
in two variables which plays an important role in
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
. It is defined for every
undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
G and contains information about how the graph is connected. It is denoted by T_G. The importance of this polynomial stems from the information it contains about G. Though originally studied in algebraic graph theory as a generalization of counting problems related to
graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...
and
nowhere-zero flow In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected (by duality) to coloring planar graphs. Definitions Let ''G'' = (''V'',''E'') be a digraph and let ''M'' be an abelian group. A ...
, it contains several famous other specializations from other sciences such as the
Jones polynomial In the mathematical field of knot theory, the Jones polynomial is a knot polynomial discovered by Vaughan Jones in 1984. Specifically, it is an invariant of an oriented knot or link which assigns to each oriented knot or link a Laurent polynomi ...
from
knot theory In the mathematical field of topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are joined so it cannot ...
and the
partition functions Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of ...
of the Potts model from
statistical physics Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approxim ...
. It is also the source of several central computational problems in
theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...
. 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 In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, elect ...
under simple transformations. It is essentially a
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
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 Graph may refer to: Mathematics * Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discr ...
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 G=(V,E) one may define the Tutte polynomial as :T_G(x,y)=\sum\nolimits_ (x-1)^(y-1)^, where k(A) denotes the number of connected components of the graph (V,A). In this definition it is clear that T_G is well-defined and a polynomial in x and y.
The same definition can be given using slightly different notation by letting r(A)=, V, -k(A) denote the
rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * ...
of the graph (V,A). Then the Whitney rank generating function is defined as :R_G(u,v)=\sum\nolimits_ u^ v^. The two functions are equivalent under a simple change of variables: :T_G(x,y)=R_G(x-1,y-1). Tutte’s dichromatic polynomial Q_G is the result of another simple transformation: :T_G(x,y)=(x-1)^ Q_G(x-1,y-1). Tutte’s original definition of T_G is equivalent but less easily stated. For connected G we set :T_G(x,y)=\sum\nolimits_ t_ x^iy^j, where t_ denotes the number of
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is ...
s of ''internal activity'' i and ''external activity'' j. A third definition uses a deletion–contraction recurrence. The edge contraction G/uv of graph G is the graph obtained by merging the vertices u and v and removing the edge uv. We write G - uv for the graph where the edge uv is merely removed. Then the Tutte polynomial is defined by the recurrence relation :T_G= T_+T_, if e is neither a
loop Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...
nor a
bridge A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually someth ...
, with base case :T_G(x,y)= x^i y^j, if G contains i bridges and j loops and no other edges. Especially, T_G=1 if G contains no edges. The
random cluster model In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, elect ...
from statistical mechanics due to provides yet another equivalent definition. The partition sum :Z_G(q,w)=\sum\nolimits_q^w^ is equivalent to T_G under the transformation :T_G(x, y)=(x-1)^(y-1)^ \cdot Z_G\Big((x-1)(y-1),\; y-1\Big).


Properties

The Tutte polynomial factors into connected components. If G is the union of disjoint graphs H and H' then : T_G= T_H \cdot T_ If G is planar and G^* denotes its dual graph then : T_G(x,y)= T_ (y,x) Especially, the chromatic polynomial of a planar graph is the flow polynomial of its dual. Tutte refers to such functions as V-functions.


Examples

Isomorphic graphs have the same Tutte polynomial, but the converse is not true. For example, the Tutte polynomial of every tree on m edges is x^m. Tutte polynomials are often given in tabular form by listing the coefficients t_ of x^iy^j in row i and column j. For example, the Tutte polynomial of the Petersen graph, :\begin 36 x &+ 120 x^2 + 180 x^3 + 170x^4+114x^5 + 56x^6 +21 x^7 + 6x^8 + x^9 \\ &+ 36y +84 y^2 + 75 y^3 +35 y^4 + 9y^5+y^6 \\ &+ 168xy + 240x^2y +170x^3y +70 x^4y + 12x^5 y \\ &+ 171xy^2+105 x^2y^2 + 30x^3y^2 \\ &+ 65xy^3 +15x^2y^3 \\ &+10xy^4, \end is given by the following table. Other example, the Tutte polynomial of the octahedron graph is given by :\begin &12\,^^+11\,x+11\,y+40\,^+32\,^+46\,yx+24\,x^+52\,x^ \\ &+25\,^+29\,^+15\,^+5\,^+6\,^x \\ &+39\,y^+20\,^+^+8\,y^ +7\,^+^ \end


History

W. T. Tutte’s interest in the deletion–contraction formula started in his undergraduate days at
Trinity College, Cambridge Trinity College is a constituent college of the University of Cambridge. Founded in 1546 by King Henry VIII, Trinity is one of the largest Cambridge colleges, with the largest financial endowment of any college at either Cambridge or Oxford. ...
, originally motivated by perfect rectangles and
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is ...
s. 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.”. R. M. Foster had already observed that the
chromatic polynomial The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to s ...
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.” 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 Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integratio ...
who knew and used analogous coefficients without bothering to affix them to two variables.” (There is “notable confusion” 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.. Independently of the work in algebraic graph theory, Potts began studying the partition function of certain models in
statistical mechanics In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic b ...
in 1952. The work by Fortuin and Kasteleyn on the
random cluster model In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, elect ...
, a generalisation of the Potts model, provided a unifying expression that showed the relation to the Tutte polynomial.


Specialisations

At various points and lines of the (x,y)-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.


Chromatic polynomial

At y=0, the Tutte polynomial specialises to the chromatic polynomial, :\chi_G(\lambda) = (-1)^ \lambda^ T_G(1-\lambda,0), where k(G) denotes the number of connected components of ''G''. For integer λ the value of chromatic polynomial \chi_G(\lambda) equals the number of vertex colourings of ''G'' using a set of λ colours. It is clear that \chi_G(\lambda) 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 \chi_G(\lambda) = \lambda^n. # If ''G'' contains a loop (a single edge connecting a vertex to itself), then \chi_G(\lambda) = 0. # If ''e'' is an edge which is not a loop, then ::\chi_G(\lambda) = \chi_(\lambda) - \chi_(\lambda). The three conditions above enable us to calculate \chi_G(\lambda), 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 \chi_G(\lambda) counts something, independently of the recurrence. In particular, :T_G(2,0) = (-1)^ \chi_G(-1) gives the number of acyclic orientations.


Jones polynomial

Along the hyperbola xy=1, the Tutte polynomial of a planar graph specialises to the
Jones polynomial In the mathematical field of knot theory, the Jones polynomial is a knot polynomial discovered by Vaughan Jones in 1984. Specifically, it is an invariant of an oriented knot or link which assigns to each oriented knot or link a Laurent polynomi ...
of an associated alternating knot.


Individual points


(2,1)

T_G(2,1) counts the number of
forest A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
s, i.e., the number of acyclic edge subsets.


(1,1)

T_G(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, T_G(1,1) counts the number of spanning trees.


(1,2)

T_G(1,2) counts the number of spanning subgraphs (edge subsets with the same number of connected components as ''G'').


(2,0)

T_G(2,0) counts the number of
acyclic orientation In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orie ...
s of ''G''..


(0,2)

T_G(0,2) counts the number of strongly connected orientations of ''G''.


(2,2)

T_G(2,2) is the number 2^ where , E, is the number of edges of graph ''G''.


(0,−2)

If ''G'' is a 4-regular graph, then :(-1)^T_G(0,-2) counts the number of
Eulerian orientation In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and end ...
s of ''G''. Here k(G) is the number of connected components of ''G''.


(3,3)

If ''G'' is the ''m'' × ''n'' grid graph, then 2 T_G(3,3) counts the number of ways to tile a rectangle of width 4''m'' and height 4''n'' with T-tetrominoes. If ''G'' is a
planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
, then 2 T_G(3,3) 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").


Potts and Ising models

Define the hyperbola in the ''xy''−plane: : H_2: \quad (x-1)(y-1)=2, the Tutte polynomial specialises to the partition function, Z(\cdot), of the
Ising model The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent ...
studied in
statistical physics Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approxim ...
. Specifically, along the hyperbola H_2 the two are related by the equation: :Z(G) = 2\left(e^\right)^ \left(4 \sinh \alpha \right )^ T_G \left (\coth \alpha, e^ \right). In particular, :(\coth \alpha - 1) \left(e^ - 1 \right ) = 2 for all complex α. More generally, if for any positive integer ''q'', we define the hyperbola: :H_q: \quad (x-1)(y-1)=q, 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 H_q.


Flow polynomial

At x=0, 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 1,2,\dots,k-1 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 C_G(k) 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 In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
, the chromatic polynomial of ''G'' is equivalent to the flow polynomial of its dual graph G^* in the sense that
Theorem (Tutte). :C_G(k)=k^ \chi_(k). The connection to the Tutte polynomial is given by: : C_G(k)= (-1)^ T_G(0,1-k).


Reliability polynomial

At x=1, 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 R_G(p), 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 :R_G(p) = (1-p)^ p^ T_G \left (1, \tfrac \right).


Dichromatic polynomial

Tutte also defined a closer 2-variable generalization of the chromatic polynomial, the dichromatic polynomial of a graph. This is :Q_G(u,v) = \sum\nolimits_ u^ v^, where k(A) is the number of connected components of the spanning subgraph (''V'',''A''). This is related to the corank-nullity polynomial by :Q_G(u,v) = u^ \, R_G(u,v). 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 m_(x) of an oriented 4-regular graph \vec was defined by Pierre Martin in 1977. He showed that if ''G'' is a plane graph and \vec_m is its directed medial graph, then :T_G(x,x) = m_(x).


Algorithms


Deletion–contraction

The deletion–contraction recurrence for the Tutte polynomial, : T_G(x,y)= T_(x,y) + T_(x,y), \qquad e \text 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 Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...
or
bridge A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually someth ...
, 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 x^my^n 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, :t(n+m)= t(n+m-1) + t(n+m-2), a recurrence relation that scales as the Fibonacci numbers with solution : t(n+m)= \left (\frac \right )^ = O \left (1.6180^ \right ). The analysis can be improved to within a polynomial factor of the number \tau(G) of spanning trees of the input graph.. For sparse graphs with m=O(n) this running time is \exp(O(n)). For regular graphs of degree ''k'', the number of spanning trees can be bounded by :\tau(G) = O \left (\nu_k^n n^ \log n \right ), where :\nu_k = \frac. so the deletion–contraction algorithm runs within a polynomial factor of this bound. For example: :\nu_5 \approx 4.4066. In practice,
graph isomorphism In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) ar ...
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 In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
efficiently computes the matrix operations
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...
and
Pfaffian In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
. These algorithms are themselves important results from algebraic graph theory and
statistical mechanics In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic b ...
. T_G(1,1) equals the number \tau(G) of
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is ...
s of a connected graph. This is computable in polynomial time as the
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...
of a maximal principal submatrix of the
Laplacian matrix In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph La ...
of ''G'', an early result in algebraic graph theory known as Kirchhoff’s Matrix–Tree theorem. Likewise, the dimension of the bicycle space at T_G(-1,-1) 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 H_2, can be expressed as a Pfaffian and computed efficiently via the
FKT algorithm The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, c ...
. This idea was developed by
Fisher Fisher is an archaic term for a fisherman, revived as gender-neutral. Fisher, Fishers or The Fisher may also refer to: Places Australia *Division of Fisher, an electoral district in the Australian House of Representatives, in Queensland *Elect ...
, Kasteleyn, and
Temperley Temperley is a district in Greater Buenos Aires, Argentina, located in the south of Lomas de Zamora Partido. History In 1854 the industrial and textile merchant George Temperley (born in 1823 in Newcastle upon Tyne, England) bought from the ...
to compute the number of
dimer Dimer may refer to: * Dimer (chemistry), a chemical structure formed from two similar sub-units ** Protein dimer, a protein quaternary structure ** d-dimer * Dimer model, an item in statistical mechanics, based on ''domino tiling'' * Julius Dimer ( ...
covers of a planar lattice model.


Markov chain Monte Carlo

Using a
Markov chain Monte Carlo In statistics, Markov chain Monte Carlo (MCMC) methods comprise a class of algorithms for sampling from a probability distribution. By constructing a Markov chain that has the desired distribution as its equilibrium distribution, one can obtain ...
method, the Tutte polynomial can be arbitrarily well approximated along the positive branch of H_2, 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 A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...
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 In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an in ...
(fpras).


Computational complexity

Several computational problems are associated with the Tutte polynomial. The most straightforward one is ;Input: A graph G ;Output: The coefficients of T_G In particular, the output allows evaluating T_G(-2,0) 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 graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
s, 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(x,y) defined for every complex pair (x,y): ;Input: A graph G ;Output: The value of T_G(x,y) The hardness of these problems varies with the coordinates (x,y).


Exact computation

If both ''x'' and ''y'' are non-negative integers, the problem T_G(x,y) 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 (x,y), one can define a rational analogue of #P.. The computational complexity of exactly computing T_G(x,y) falls into one of two classes for any x, y \in \mathbb. The problem is #P-hard unless (x,y) lies on the hyperbola H_1 or is one of the points :\left \, \qquad j = e^. 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 H_2 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 T_G(0,-2), 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 mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sha ...
. 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 In computational complexity theory and game complexity, a parsimonious reduction is a transformation from one problem to another (a reduction) that preserves the number of solutions. Informally, it is a bijection between the respective sets of so ...
.


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 T_G(x,y) is Jerrum and Sinclair’s FPRAS, which works for points on the “Ising” hyperbola H_2 for ''y'' > 0. If the input graphs are restricted to dense instances, with degree \Omega(n), there is an FPRAS if ''x'' ≥ 1, ''y'' ≥ 1.For the case ''x'' ≥ 1 and ''y'' = 1, see . For the case ''x'' ≥ 1 and ''y'' > 1, see . 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.


See also

* Bollobás–Riordan polynomial * A Tutte–Grothendieck invariant is any evaluation of the Tutte polynomial


Notes


References

*. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *.


External links

* * {{MathWorld , urlname=TuttePolynomial, title=Tutte polynomial *
PlanetMath PlanetMath is a free, collaborative, mathematics online encyclopedia. The emphasis is on rigour, openness, pedagogy, real-time content, interlinked content, and also community of about 24,000 people with various maths interests. Intended to be c ...
br>Chromatic polynomial
* Steven R. Pagano

* Sandra Kingan
Matroid theory
Many links. * Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle

Computational problems Duality theories Matroid theory Polynomials Graph invariants