Transforming polynomials

2013-03-25T01:59:11Z

129.97.125.145: /* Reciprocals of the roots */

{{about|the Tutte polynomial of a graph|the Tutte polynomial of a matroid|Matroid}}

[[Image:Tutte polynomial and chromatic polynomial of the Bull graph.jpg|thumb|300px|right|The polynomial <math>x^4+x^3+x^2y</math> is the Tutte polynomial of the [[Bull graph]]. The red line shows the intersection with the plane <math>y=0</math>, equivalent to the chromatic polynomial.]]

The '''Tutte polynomial''', also called the '''dichromate''' or the '''Tutte–Whitney polynomial''', is a [[polynomial]] in two variables which plays an important role in [[graph theory]], a branch of [[mathematics]] and [[theoretical computer science]]. It is defined for every [[undirected graph]] and contains information about how the graph is connected.

The importance of the Tutte polynomial <math>T_G</math> comes from the information it contains about ''G''. Though originally studied in [[algebraic graph theory]] as a generalisation of counting problems related to [[graph coloring]] and [[nowhere-zero flow]], it contains several famous other specialisations 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 problem]]s 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 generalisations to [[matroid]]s. 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.<ref>Chap. 10 in {{harvtxt|Bollobás|1998}}, chap. 13 in {{harvtxt|Biggs|1993}}, chap. 15 in {{harvtxt|Godsil|Royle|2004}}.</ref>

==Definitions==
<blockquote>'''Definition.''' For an undirected graph <math>G=(V,E)</math> one may define the '''Tutte polynomial''' as

:<math>T_G(x,y)=\sum\nolimits_{A\subseteq E} (x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|},</math>

where <math>k(A)</math> denotes the number of [[connected component (graph theory)|connected component]]s of the graph <math>(V,A)</math>. In this definition it is clear that <math>T_G</math> is well-defined and a polynomial in ''x'' and ''y''.</blockquote>

The same definition can be given using slightly different notation by letting <math>r(A)=|V|-k(A)</math> denote the [[rank (graph theory)|rank]] of the graph <math>(V,A)</math>. Then the '''Whitney rank generating function''' is defined as

:<math>R_G(x,y)=\sum\nolimits_{A\subseteq E} x^{r(E)-r(A)} y^{|A|-r(A)}</math>

the two functions are equivalent under a simple change of variables:

:<math>T_G(x,y)=R_G(x-1,y-1).</math>

Tutte’s '''dichromatic polynomial''' <math>Q_G</math> is the result of another simple transformation:

:<math>T_G(x,y)=(x-1)^{-k(G)} Q_G(x-1,y-1).</math>

Tutte’s original definition of <math>T_G</math> is equivalent but less easily stated. For connected ''G'' we set

:<math>T_G(x,y)=\sum\nolimits_{i,j} t_{ij} x^iy^j,</math>

where <math>t_{ij}</math> denotes the number of [[Spanning tree (mathematics)|spanning tree]]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

:<math>T_G= T_{G-e}+T_{G/e},</math>

if ''e'' is neither a [[Loop (graph theory)|loop]] nor a [[Bridge (graph theory)|bridge]], with base case

:<math>T_G(x,y)= x^i y^j, </math>

if ''G'' contains ''i'' bridges and ''j'' loops and no other edges. Especially, <math>T_G=1</math> if ''G'' contains no edges.

The '''random cluster model''' from statistical mechanics due to {{harvtxt|Fortuin|Kasteleyn|1972}} provides yet another equivalent definition.<ref>cf. {{harvtxt|Sokal|2005}}</ref> The polynomial

:<math>Z_G(q,w)=\sum\nolimits_{F\subseteq E}q^{k(F)}w^{|F|}</math>

is equivalent to <math>T_G</math> under the transformation<ref>eq. (2.26) in {{harvtxt|Sokal|2005}}</ref>

:<math>T_G(x, y)=(x-1)^{-k(E)}(y-1)^{-|V|} \cdot Z_G\Big((x-1)(y-1),\; y-1\Big).</math>

===Properties===
The Tutte polynomial factors into connected components: If ''G'' is the union of disjoint graphs ''H'' and <math>H'</math> then
: <math>T_G= T_H \cdot T_{H'}</math>

If ''G'' is planar and <math>G^*</math> denotes its [[dual graph]] then

: <math>T_G(x,y)= T_{G^*} (y,x)</math>

Especially, the chromatic polynomial of a planar graph is the flow polynomial of its dual.

===Examples===
Isomorphic graphs have the same Tutte polynomial, but the opposite is not true. For example, the Tutte polynomial of every tree on ''m'' edges is <math>x^m</math>.

Tutte polynomials are often given in tabular form by listing the coefficients <math>t_{ij}</math> of <math>x^iy^j</math> in row ''i'' and column ''j''. For example, the Tutte polynomial of the [[Petersen graph]],

:<math>\begin{align}
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{align}</math>

is given by the following table.

{|class="wikitable"
| 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
|}

==History==
[[W. T. Tutte]]’s interest in the [[deletion–contraction formula]] started in his undergraduate days at [[Trinity College, Cambridge]], originally motivated by [[perfect rectangle]]s and [[Spanning tree (mathematics)|spanning tree]]s. He often applied the formula in his research and “wondered if there were other interesting [[graph invariant|functions of graphs, invariant under isomorphism]], with similar recursion formulae.”<ref name="harvtxt|Tutte|2004">{{harvtxt|Tutte|2004}}</ref> [[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 delection–contraction recursion was ''W-function'' (and ''V-function'' if multiplicative over component). Tutte writes, “Playing with my ''W-functions'' I obtained a two-variable polynomial from which either the chromatic polynomial or the ﬂow-polynomial could be obtained by setting one of the variables equal to zero, and adjusting signs.”<ref name="harvtxt|Tutte|2004"/> 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 coefﬁcients without bothering to afﬁx them to two variables.” There is “notable confusion” <ref>Welsh</ref> about the terms ''dichromate'' and ''dichromatic polynomial'', introduced by Tutte in different papers and differ slightly. The generalisation of the Tutte polynomial to matroids was first published by Crapo, though it appears already in Tutte’s thesis.<ref>See {{harvtxt|Farr|2007}}</ref>

Independently of the work in [[algebraic graph theory]], Potts began studying the [[partition function (statistical mechanics)|partition function]] of certain models in [[statistical mechanics]] in 1952. The work of {{harvtxt|Fortuin|Kasteleyn|1972}} on the [[random cluster model]], a generalisation of [[Potts model]], provided a unifying expression that showed the relation to the Tutte polynomial.<ref>{{harvtxt|Farr|2007}}</ref>

== Specialisations==
At various points and lines of the <math>(x,y)</math>-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===
{{Main|Chromatic polynomial}}

[[Image:Chromatic in the Tutte plane.jpg|thumb|right|The chromatic polynomial drawn in the Tutte plane]]

At <math>y=0</math>, the Tutte polynomial specialises to the chromatic polynomial,

:<math>\chi_G(\lambda) = (-1)^{|V|-k(G)} \lambda^{k(G)} T_G(1-\lambda,0),</math>
where <math>k(G)</math> denotes the number of connected components of ''G''.

For integer λ the value of chromatic polynomial <math>\chi_G(\lambda)</math> equals the number of [[vertex colouring]]s of ''G'' using a set of λ colours. It is clear that <math>\chi_G(\lambda)</math> 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 <math>\chi_G(\lambda) = \lambda^n</math>.
# If ''G'' contains a loop (a single edge connecting a vertex to itself), then <math>\chi_G(\lambda) = 0</math>.
# If ''e'' is an edge which is not a loop, then
::<math>\chi_G(\lambda) = \chi_{G\setminus e}(\lambda) - \chi_{G/e}(\lambda).</math>

The three conditions above enable us to calculate <math>\chi_G(\lambda)</math>, 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 <math>\chi_G(\lambda)</math> counts something, independently of the recurrence. In particular,

:<math>T_G(2,0) = (-1)^{|V|} \chi_G(-1)</math>

gives the number of acyclic orientations.

===Jones polynomial===
{{Main|Jones polynomial}}

[[Image:Jones in the Tutte plane.jpg|thumb|right|The Jones polynomial drawn in the Tutte plane]]

Along the hyperbola <math>xy=1</math>, the Tutte polynomial specialises to the [[Jones polynomial]] of an [[alternating knot]] if ''G'' is planar.

===Individual points===
====(2,1)====
<math>T_G(2,1)</math> counts the number of [[tree (graph theory)|forest]]s, i.e., the number of acyclic edge subsets.
====(1,1)====
<math>T_G(1,1)</math> counts the number of spanning forests (edge subsets without cycles and the same number of connected components as ''G'').
====(1,2)====
<math>T_G(1,2)</math> counts the number of spanning subgraphs (edge subsets with the same number of connected components as ''G'').
====(2,0)====
<math>T_G(2,0)</math> counts the number of [[acyclic orientation]]s of ''G''.<ref name="welsh99">{{harvtxt|Welsh|1999}}</ref>
====(0,2)====
<math>T_G(0,2)</math> counts the number of [[Robbins theorem|strongly connected orientations]] of ''G''.<ref>{{harvtxt|Las Vergnas|1980}}.</ref>
====(0,−2)====
If ''G'' is a 4-regular graph, then
:<math>(-1)^{|V|+k(G)}T_G(0,-2)</math>
counts the number of [[Eulerian orientation]]s of ''G''. Here <math>k(G)</math> is the number of connected components of ''G''.<ref name="welsh99"/>
====(3,3)====
If ''G'' is the ''m'' × ''n'' [[grid graph]], then <math>2 T_G(3,3)</math> counts the number of ways to tile a rectangle of width 4''m'' and height 4''n'' with [[tetromino|T-tetrominoes]].<ref>{{harvtxt|Korn|Pak|2004}}, see also {{harvtxt|Korn|Pak|2003}} for combinatorial interpretations of many other points</ref>

If ''G'' is a [[planar graph]], then <math>2 T_G(3,3)</math> 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").<ref>{{harvtxt|Las Vergnas|1988}}</ref>

===Potts and Ising models===
{{Main|Ising model|Potts model}}

[[Image:Potts and Ising in the Tutte plane.jpg|thumb|right|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:

:<math> H_2: \quad (x-1)(y-1)=2,</math>

the Tutte polynomial specialises to the partition function, <math>Z(\cdot),</math> of the [[Ising model]] studied in [[statistical physics]]. Specifically, along the hyperbola <math>H_2</math> the two are related by the equation:<ref>{{cite book
| last = Welsh
| first = Dominic
| authorlink = Dominic Welsh
| title = Complexity: Knots, Colourings and Counting
| series = London Mathematical Society Lecture Note Series
| year = 1993
| publisher = Cambridge University Press
| isbn = 978-0521457408
| page = 62
}}</ref>

:<math>Z(G) = 2\left(e^{-\alpha}\right)^{|E| - r(E)} \left(4 \sinh \alpha \right )^{r(E)} T_G \left (\coth \alpha, e^{2 \alpha} \right).</math>

In particular,

:<math>(\coth \alpha - 1) \left(e^{2 \alpha} - 1 \right ) = 2</math>

for all complex α.

More generally, if for any positive integer ''q'', we define the hyperbola:

:<math>H_q: \quad (x-1)(y-1)=q,</math>

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 <math>H_q</math>.

{|class="wikitable" style="margin: 1em auto 1em auto"
|+ Correspondences between the Potts model and the Tutte plane <ref>{{harvtxt|Welsh|Merino|2000}}</ref>
! Potts model || Tutte polynomial
|-
| [[Ferromagnetism|Ferromagnetic]]
|| Positive branch of <math>H_q</math>
|-
| [[Antiferromagnetism|Antiferromagnetic]]
|| Negative branch of <math>H_q</math> with <math>y>0</math>
|-
| High temperature
|| Asymptote of <math>H_q</math> to <math>y=1</math>
|-
| Low temperature ferromagnetic
|| Positive branch of <math>H_q</math> asymptotic to <math>x=1</math>
|-
| Zero temperature antiferromagnetic
|| [[Graph coloring|Graph ''q''-colouring]], i.e., <math>x=1-q, y=0</math>
|}

===Flow polynomial===
{{Main|Nowhere-zero flow}}

[[Image:Flow in the Tutte plane.jpg|thumb|right|The flow polynomial drawn in the Tutte plane]]

At <math>x=0</math>, 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 <math>1,2,\dots,k-1</math> 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 <math>C_G(k)</math> 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]] <math>G^*</math> in the sense that

<blockquote>'''Theorem (Tutte).'''

:<math>C_G(k)=k^{-1} \chi_{G^*}(k).</math>

The connection to the Tutte polynomial is given by:

: <math>C_G(k)= (-1)^{|E|+|V|+k(G)} T_G(0,1-k).</math></blockquote>

===Reliability polynomial===
{{Main|Connectivity (graph theory)}}

[[Image:Reliability in the Tutte plane.jpg|thumb|right|The reliability polynomial drawn in the Tutte plane]]

At <math>x=1</math>, 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 <math>R_G(p)</math>, 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

:<math>R_G(p) = (1-p)^{|V|-k(G)} p^{|E|-|V|+k(G)} T_G \left (1, \tfrac{1}{p} \right).</math>

===Dichromatic polynomial===
Tutte also defined a closer 2-variable generalization of the chromatic polynomial, the '''dichromatic polynomial''' of a graph. This is

:<math>Q_G(u,v) = \sum\nolimits_{A \subseteq E} u^{k(A)} v^{|A|-|V|+k(A)},</math>

where <math>k(A)</math> is the number of [[connected component (graph theory)|connected components]] of the spanning subgraph (''V'',''A''). This is related to the '''corank-nullity polynomial''' by

:<math>Q_G(u,v) = u^{k(G)} \, R_G(u,v).</math>

The dichromatic polynomial does not generalize to matroids because ''c''(''A'') is not a matroid property: different graphs with the same matroid can have different numbers of connected components.

==Related polynomials==
===Martin polynomial===
{{main|Martin polynomial}}
The Martin polynomial <math>m_{\vec{G}}(x)</math> of an oriented 4-regular graph <math>\vec{G}</math> was defined by Pierre Martin in his 1977 thesis.<ref> {{Cite thesis |last=Martin |first=Pierre |title=Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck
|trans_title=Eulerian Enumerations in multigraphs and Tutte-Grothendieck invariants |language=French |publisher=[[Joseph Fourier University]] |url=http://tel.archives-ouvertes.fr/tel-00287330/en |year=1977}} </ref> In this work, Martin showed that if ''G'' is a plane graph and <math>\vec{G}_m</math> is its [[Medial_graph#Directed_medial_graph|directed medial graph]], then

:<math>T_G(x,x) = m_{\vec{G}_m}(x).</math>

==Algorithms==
===Deletion–contraction===
[[Image:deletion-contraction.svg|thumb|right|300px|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, <math>x^3+2x^2 +y^2+2xy+x+y</math>. Based on {{harvtxt|Welsh|Merino|2000}}.]]

The deletion–contraction recurrence for the Tutte polynomial,
: <math>T_G(x,y)= T_{G \setminus e}(x,y) + T_{G/e}(x,y), \qquad e \text{ not a loop nor a bridge.} </math>
immediately yields a recursive algorithm for computing it: choose any such edge ''e'' and repeatedly apply the formula until all edges are either loops or bridges; the resulting base cases at the bottom of the evaluation are easy to compute.

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,
:<math>t(n+m)= t(n+m-1) + t(n+m-2),</math>
a recurrence relation that scales as the [[Fibonacci numbers]] with solution<ref>{{harvtxt|Wilf|1986}}</ref>

:<math> t(n+m)= \left (\frac{1+\sqrt{5}}{2} \right )^{n+m} = O \left (1.6180^{n+m} \right ).</math>

The analysis can be improved to within a polynomial factor of the number <math>\tau(G)</math> of [[spanning tree (mathematics)|spanning trees]] of the input graph.<ref>{{harvtxt|Sekine|Imai|Tani|1995}}</ref> For sparse graphs with <math>m=O(n)</math> this running time is <math>O(\exp(n))</math>. For regular graphs of degree ''k'', the number of spanning trees can be bounded by

:<math>\tau(G) = O \left (\nu_k^n n^{-1} \log n \right ),</math>

where

:<math>\nu_k = \frac{(k-1)^{k-1}}{(k^2-2k)^{\frac{k}{2}-1}}.</math>

so the deletion–contraction algorithm runs within a polynomial factor of this bound. For example:<ref>{{harvtxt|Chung|Yau|1999}}, following {{harvtxt|Björklund|Husfeldt|Kaski|Koivisto|2008}}</ref>

:<math>\nu_5 \approx 4.4066.</math>

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''.<ref>{{harvtxt|Sekine|Imai|Tani|1995}}, {{harvtxt|Imai|2000}}, {{harvtxt|Haggard|Pierce|Royle|2008}}</ref>

===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]].

<math>T_G(1,1)</math> equals the number <math>\tau(G)</math> of [[Spanning tree (mathematics)|spanning tree]]s 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 <math>T_G(-1,-1)</math> 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 <math>H_2</math>, can be expressed as a Pfaffian and computed efficiently via the [[FKT algorithm]]. This idea was developed by [[Michael Fisher|Fisher]], [[Pieter Kasteleyn|Kasteleyn]], and [[Harold Neville Vazeille Temperley|Temperley]] to compute for the number of [[domino tiling|dimer]] covers of a planar [[Lattice model (physics)|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 <math>H_2</math>, equivalently, the partition function of the ferromagnetic Ising model. This exploits the close connection between the Ising model and the problem of counting [[Matching (graph theory)|matchings]] in a graph. The idea behind this celebrated result of Jerrum and Sinclair<ref>{{harvtxt|Jerrum|Sinclair|1993}}</ref> 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 ''G''
;Output
:The coefficients of <math>T_G</math>
In particular, the output allows evaluating <math>T_G(-2,0)</math> which is equivalent to counting the number of 3-colourings of ''G''. This latter question is [[Sharp-P-complete|#P-complete]], even when restricted to the family of [[planar graph]]s, so the problem of computing the coefficients of the Tutte polynomial for a given graph is [[Sharp-P-hard|#P-hard]] even for planar graphs.

Much more attention has been given to the family of problems called Tutte<math>(x,y)</math> defined for every complex pair <math>(x,y)</math>:
;Input
:A graph ''G''
;Output
:The value of <math>T_G(x,y)</math>
The hardness of these problems varies with the coordinates <math>(x,y)</math>.

===Exact computation===
[[Image:Tractable points of the Tutte polynomial in the real plane.svg|thumb|300px|right|
The Tutte plane.
Every point <math>(x,y)</math> in the real plane corresponds to a computational problem <math>T_G(x,y)</math>.
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 <math>T_G(x,y)</math> belongs to [[Sharp-P|#P]]. For general integer pairs, the Tutte polynomial contains negative terms, which places the problem in the complexity class [[GapP]], the closure of [[Sharp-P|#P]] under subtraction. To accommodate rational coordinates <math>(x,y)</math>, one can define a rational analogue of [[Sharp-P|#P]].<ref name="harvtxt|Goldberg |Jerrum |2008"> {{harvtxt|Goldberg|Jerrum|2008}}</ref>

The computational complexity of exactly computing <math>T_G(x,y)</math> falls into one of two classes for any <math>x, y \in \mathbb{C}</math>. The problem is #P-hard unless <math>(x,y)</math> lies on the hyperbola <math>H_1</math> or is one of the points

:<math>\left \{ (1,1), (-1,-1), (0,-1), (-1,0), (i,-i), (-i,i), \left(j,j^2 \right), \left(j^2,j \right) \right \}, \qquad j = e^{\frac{2 \pi i}{3}}.</math>

In which cases it is computable in polynomial time.<ref>{{harvtxt|Jaeger|Vertigan|Welsh|1990}}</ref> If the problem is restricted to the class of planar graphs, the points on the hyperbola <math>H_2</math> become polynomial-time computable as well. All other points remain #P-hard, even for bipartite planar graphs.<ref>{{harvtxt|Vertigan|Welsh|1992}}</ref> 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 <math>T_G(0,-2)</math>, which counts nowhere-zero '''Z'''<sub>3</sub>-flows and is computable in polynomial time.<ref>{{cite journal | last = Vertigan | first = Dirk | year = 2005 | title = The Computational Complexity of Tutte Invariants for Planar Graphs | journal = SIAM J. Comput. | volume = 35 | issue = 3 | pages = 690–712 | doi = 10.1137/S0097539704446797 | url = http://dx.doi.org/10.1137/S0097539704446797 }}</ref>

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-colourings of a planar graph is #P-complete, even though the decision problem is trivial by the [[four color theorem|four colour theorem]]. In contrast, it is easy to see that counting the number of three-colourings 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 <math>T_G(x,y)</math> is Jerrum and Sinclair’s FPRAS, which works for points on the “Ising” hyperbola <math>H_2</math> for ''y'' > 0. If the input graphs are restricted to dense instances, with degree <math>\Omega(n)</math>, there is an FPRAS if ''x'' ≥ 1, ''y'' ≥ 1.<ref>''x'' ≥ 1, ''y'' = 1 is given by {{harvtxt|Annan|1994}}. ''x'' ≥ 1, ''y'' > 1 is given by {{harvtxt|Alon|Frieze|Welsh|1995}}</ref>

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.<ref name="harvtxt|Goldberg |Jerrum |2008" />

==See also==
[[Bollobás–Riordan polynomial]]

==Notes==
{{Reflist|colwidth=25em}}

== References ==
{{refbegin|colwidth=25em}}
*{{Citation
|last1=Alon|first1=N.
|last2=Frieze|first2=A.
|last3=Welsh|first3= D. J. A.|authorlink3=Dominic Welsh
|journal= Random Structures and Algorithms
|title=Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case
| volume= 6| issue= 4| pages= 459–478| doi=10.1002/rsa.3240060409 |year=1995
}}
*{{Citation
|doi=10.1017/S0963548300001188
|last1=Annan |first1= J. D.
|title=A randomised approximation algorithm for counting the number of forests in dense graphs
|journal=Combin. Prob. Comput.
|volume=3 |year=1994|pages= 273–283
|issue=3
}}
*{{Citation | author=Biggs, Norman | title=Algebraic Graph Theory | edition=2nd | location=Cambridge | publisher=Cambridge University Press | year=1993 | isbn=0-521-45897-8}}
*{{Citation
| first1=Andreas | last1=Björklund
| first2=Thore | last2=Husfeldt
| first3=Petteri | last3=Kaski
| first4=Mikko | last4=Koivisto
| title = Computing the Tutte polynomial in vertex-exponential time
| journal = Proceedings of the 47th annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
| pages=677–686
| year = 2008
| doi= 10.1109/FOCS.2008.40
| isbn=978-0-7695-3436-7
}}
* {{Citation | last1=Bollobás | first1=Béla | author1-link=Béla Bollobás | title=Modern Graph Theory | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-98491-9 | year=1998}}
* Henry H. Crapo (1969), The Tutte polynomial. ''Aequationes Mathematicae'', volume 3, pp. 211–229.
*{{Citation | last= Farr | first= Graham E. | editor1-last=Grimmett | editor1-first=Geoffrey| editor1-link=Geoffrey Grimmett | editor2-last=McDiarmid | editor2-first=Colin | title=Combinatorics, complexity, and chance. A tribute to Dominic Welsh | series=Oxford Lecture Series in Mathematics and its Applications | volume=34 | location=Oxford | publisher=[[Oxford University Press]] | year=2007 | isbn=0-19-857127-5 |contribution= Tutte-Whitney polynomials: some history and generalizations | pages= 28–52 | zbl=1124.05020 }}
*{{Citation
| title=On the random-cluster model: I. Introduction and relation to other models
| last1 = Fortuin | first1 = Cees M.
| last2 = Kasteleyn | first2 = Pieter W.
| journal=Physica
| volume=57
| pages=536–564
| issn=0031-8914
| year=1972
| publisher=Elsevier
| doi=10.1016/0031-8914(72)90045-6
| issue=4
}}
*{{Citation | last1=Godsil | first1=Chris | authorlink1=Chris Godsil|last2=Royle | first2=Gordon |authorlink2=Gordon Royle| title=Algebraic Graph Theory | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-95220-8 | year=2004}}
*{{Citation
|last1=Goldberg | first1= L.A.
|last2=Jerrum | first2= M.
|author2-link=Mark Jerrum
|title= Inapproximability of the Tutte polynomial
|journal=Information and Computation
| doi=10.1016/j.ic.2008.04.003
|year=2008
|volume=206
|page=908
|issue=7
}}
*{{Citation
| last1= Jaeger |first1= F.
|last2= Vertigan | first2= D. L.
|last3= Welsh | first3 =D. J. A.|authorlink3=Dominic Welsh
| title= On the computational complexity of the Jones and Tutte polynomials
|journal=Mathematical Proceedings of the Cambridge Philosophical Society
| volume= 108|pages = 35–53
| doi= 10.1017/S0305004100068936
| year= 1990
}}
*{{Citation
|last1= Jerrum | first1=M.
|author-link=Mark Jerrum
|last2= Sinclair | first2= A.
|author2-link= Alistair Sinclair
|title= Polynomial-time approximation algorithms for the Ising model
|journal= SIAM J. Comput.
|volume=22|year=1993|pages=1087–1116
|doi= 10.1137/0222066
|issue= 5
}}
*{{Citation
|last1= Korn | first1=M.
|last2= Pak | first2= I.
|author2-link= Igor Pak
|title=Combinatorial evaluations of the Tutte polynomial
|journal= Preprint
|year= 2003
}}
*{{Citation
|last1= Korn | first1=M.
|last2= Pak | first2= I.
|author2-link= Igor Pak
|title=Tilings of rectangles with T-tetrominoes
|journal= Theor. Comp. Science
|volume= 319|year= 2004|pages= 3–27
|doi= 10.1016/j.tcs.2004.02.023
}}
*{{citation
| last = Las Vergnas | first = Michel | authorlink = Michel Las Vergnas
| doi = 10.1016/0095-8956(80)90082-9
| issue = 2
| journal = [[Journal of Combinatorial Theory]] | series = Series B
| mr = 586435
| pages = 231–243
| title = Convexity in oriented matroids
| volume = 29
| year = 1980}}
*{{citation
| last1 = Las Vergnas
| first1 = Michel
| year = 1988
| title = On the evaluation at (3, 3) of the Tutte polynomial of a graph
| journal = Journal of Combinatorial Theory, Series B
| volume = 35
| issue = 3
| pages = 367–372
| issn = 0095-8956
| doi = 10.1016/0095-8956(88)90079-2
| url = http://www.sciencedirect.com/science/article/pii/0095895688900792
}}
*{{Citation
| last=Sokal | first=Alan D.
| title = The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
| booktitle = Surveys in Combinatorics
| year = 2005
| volume = 327
| pages = 173–226
| series = London Mathematical Society Lecture Note Series
| arxiv = math/0503607
}}
*{{Citation
|last= Tutte | first= W. T.
| title=Graph Theory
| year=2001
| isbn=978-0521794893
| publisher=Cambridge University Press
}}
*{{Citation
|last= Tutte | first= W. T.
| title= Graph-polynomials
| journal= Advances in Applied Mathematics
| volume =32
| year=2004
| pages= 5–9
|doi= 10.1016/S0196-8858(03)00041-1
}}
*{{citation
| last1 = Vertigan
| first1 = D. L.
| last2 = Welsh
| first2 = D. J. A.|authorlink2= Dominic Welsh
| year = 1992
| title = The Computational Complexity of the Tutte Plane: the Bipartite Case
| journal = Combinatorics, Probability and Computing
| volume = 1
| issue = 2
| pages = 181–187
| doi = 10.1017/S0963548300000195
| url = http://dx.doi.org/10.1017/S0963548300000195
}}
*{{Citation
|last= Welsh | first= D. J. A.
| title=Matroid Theory
| year=1976
| isbn=012744050X
| publisher=Academic Press London
}}
*{{citation
| last = Welsh
| first = Dominic|authorlink=Dominic Welsh
| year = 1999
| title = The Tutte polynomial
| journal = Random Structures & Algorithms
| volume = 15
| issue = 3–4
| pages = 210–228
| publisher = John Wiley & Sons, Inc.
| issn = 1042-9832
| doi = 10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R
| url = http://dx.doi.org/10.1002/(SICI)1098-2418(199910/12)15:3/4%3C210::AID-RSA2%3E3.0.CO;2-R
}}
*{{Citation
| last1= Welsh | first1= D. J. A.|authorlink1=Dominic Welsh
| last2= Merino | first2= C.
| title=The Potts model and the Tutte polynomial
| journal = Journal of Mathematical Physics
| volume = 41 | issue= 3 | date= March 2000 }}
{{refend}}

== External links ==
* {{springer|title=Tutte polynomial|id=p/t120210}}
* {{MathWorld | urlname=TuttePolynomial| title=Tutte polynomial}}
* [[PlanetMath]] [http://planetmath.org/encyclopedia/ChromaticPolynomial.html Chromatic polynomial]
* Steven R. Pagano: [http://www.ms.uky.edu/~pagano/Matridx.htm Matroids and Signed Graphs]
* Sandra Kingan: [http://members.aol.com/matroids/ Matroid theory]. Lots of links.
* Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [http://www.ecs.vuw.ac.nz/~djp/tutte/]

[[Category:Computational problems]]
[[Category:Duality theories]]
[[Category:Matroid theory]]
[[Category:Polynomials]]
[[Category:Graph invariants]]

formulasearchengine - User contributions [en]

Transforming polynomials