ECCC-Report TR94-005 and Revisions published for TR94-005en-usMon, 12 Dec 1994 00:00:00 +0200 Paper TR94-005 | Polynomial time randomised approximation schemes for Tutte-Gr\&quot;{o}thendieck invariants: the dense case | Noga Alon, Alan Frieze, Dominic Welsh Tutte-Gr\&quot;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 &gt; 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. Mon, 12 Dec 1994 00:00:00 +0200