ECCC-Report TR94-005https://eccc.weizmann.ac.il/report/1994/005Comments 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\"{o}thendieck invariants: the dense case |
Noga Alon,
Alan Frieze,
Dominic Welsh
https://eccc.weizmann.ac.il/report/1994/005The 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.
Mon, 12 Dec 1994 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/005