TY - JOUR
T1 - Polynomial time randomised approximation schemes for the Tutte polynomial of dense graphs
AU - Alon, Noga
AU - Frieze, Alan
AU - Welsh, Dominic
N1 - Funding Information:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. Email: noga@math.tau.ac.il. Research supported in part by a USA-Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences. 'Department of Mathematics, Carnegie Mellon University, Pittsburgh PA15213, U.S.A., Supported by NSF grant CCR- 9225008 *Merton College and Mathematical Institute, Oxford, UK. Research supported in part by ESPRIT RAND.
Publisher Copyright:
© 1994 IEEE
PY - 1994
Y1 - 1994
N2 - The Tutte-Grothendieck 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 Ω(n), whenever x 1 and y 1, and in various additional points. 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.
AB - The Tutte-Grothendieck 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 Ω(n), whenever x 1 and y 1, and in various additional points. 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.
UR - http://www.scopus.com/inward/record.url?scp=0002880455&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0002880455&partnerID=8YFLogxK
U2 - 10.1109/SFCS.1994.365708
DO - 10.1109/SFCS.1994.365708
M3 - Conference article
AN - SCOPUS:0002880455
SN - 0272-5428
SP - 24
EP - 35
JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
T2 - Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science
Y2 - 20 November 1994 through 22 November 1994
ER -