Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case

This is the authors' abstract. We don't add key points for this paper.

The Tutte‐Gröthendieck 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.