Inapproximability of the Tutte polynomial

Details Inapproximability of the Tutte polynomial Inapproximability of the Tutte polynomial

2006-05-30

arxiv.org/abs/cs/0605140v2

Infomation and Computation 206(7), 908-929 (July 2008)

Computer Science

Computational Complexity

Minor changes to correct typos and provide clarification. Also includes an extra figure

Scientific paper

10.1016/j.ic.2008.04.003

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 \lambda>2 is a positive integer. Thus there is no FPRAS for counting nowhere-zero \lambda flows for \lambda>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for \lambda=6.

Affiliated with

Also associated with

No associations

Rating

Inapproximability of the Tutte polynomial does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Inapproximability of the Tutte polynomial, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inapproximability of the Tutte polynomial will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-467166