2006/05/31 by Leslie Ann Goldberg, Mark Jerrum
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Graph theory and applications #Markov Chains and Monte Carlo Methods #cs.CC #math.CO
paper · pdf · doi:10.1016/j.ic.2008.04.003
published as Infomation and Computation 206(7), 908-929 (July 2008) · Minor changes to correct typos and provide clarification. Also includes an extra figure
arxiv created 2007/07/30 · openalex publication_date 2008/05/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger, Vertigan and Welsh have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a "fully polynomial randomised approximation scheme" (FPRAS) for T(G;x,y). Under the assumption RP is not equal to NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1, y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP is not equal to NP, there is no FPRAS at the point (x,y)=(0,1--lambda) when λ>2 is a positive integer. Thus there is no FPRAS for counting nowhere-zero λflows for λ>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ=6.