Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR94-005 | 12th December 1994 00:00

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


Authors: Noga Alon, Alan Frieze, Dominic Welsh
Publication: 12th December 1994 00:00
Downloads: 1012


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.

ISSN 1433-8092 | Imprint