__
TR94-005 | 12th December 1994 00:00
__

#### Polynomial time randomised approximation schemes for Tutte-Gr\"{o}thendieck invariants: the dense case

**Abstract:**
The Tutte-Gr\"othendieck polynomial $T(G;x,y)$ of a graph $G$

encodes numerous interesting combinatorial quantities associated

with the graph. Its evaluation in various points in the $(x,y)$

plane give the number of spanning forests of the graph, the number

of its strongly connected orientations, the number of its proper

$k$-colorings, the (all terminal) reliability probability of the

graph, and various other invariants the exact computation of each

of which is well known to be $\#P$-hard. Here we develop a general

technique that supplies fully polynomial randomised approximation

schemes for approximating the value of $T(G;x,y)$ for any dense

graph $G$, that is, any graph on

$n$ vertices whose minimum degree is $\Omega(n)$, whenever

$x \geq 1$ and $y > 1$, and in various additional points.

Annan \cite{1} has dealt with the case $y=1$, $x\geq 1$.

This region includes evaluations of reliability and partition

functions of the ferromagnetic $Q$-state Potts model.

Extensions to linear matroids where $T$ specialises to the

weight enumerator of linear codes are considered as well.