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.