POLYNOMIAL-TIME RANDOMIZED APPROXIMATION SCHEMES FOR TUTTE-GROTHENDIECK INVARIANTS - THE DENSE CASE

The Tutte-Grothendieck polynomial T(G; x, y) of a graph G encodes nume rous interesting combinatorial quantities associated with the graph. I ts evaluation in various points in the (x, y) plane give the number of spanning forests of the graph, the number of its strongly connected o rientations, 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 randomis ed 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 deg ree is Omega(n), whenever x greater than or equal to 1 and y > 1, and in various additional points. Annan has dealt with the case y = 1, x g reater than or equal to 1. This region includes evaluations of reliabi lity and partition functions of the ferromagnetic e-state Potts model. Extensions to linear matroids where T specialises to the weight enume rator of linear codes are considered as well. (C) 1995 John Wiley & So ns, Inc.