Inapproximability of the Tutte polynomial of a planar graph

Details Inapproximability of the Tutte polynomial of a planar graph Inapproximability of the Tutte polynomial of a planar graph

2009-07-10

arxiv.org/abs/0907.1724v3

Computer Science

Computational Complexity

In this revision, significant changes have been made to the structure of the paper to clarify the presentation. Extra detail h

Scientific paper

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: given as input a planar graph G, determine T(G;x,y). Vertigan completely mapped the complexity of exactly computing the Tutte polynomial of a planar graph. He showed that the problem can be solved in polynomial time if (x,y) is on the hyperbola H_q given by (x-1)(y-1)=q for q=1 or q=2 or if (x,y) is one of the two special points (x,y)=(-1,-1) or (x,y)=(1,1). Otherwise, the problem is #P-hard. In this paper, we consider the problem of approximating T(G;x,y), in the usual sense of "fully polynomial randomised approximation scheme" or FPRAS. Roughly speaking, an FPRAS is required to produce, in polynomial time and with high probability, an answer that has small relative error. Assuming that NP is different from RP, we show that there is no FPRAS for the Tutte polynomial in a large portion of the (x,y) plane. In particular, there is no FPRAS if x>1, y<-1 or if y>1, x<-1 or if x<0, y<0 and q>5. Also, there is no FPRAS if x<1, y<1 and q=3. For q>5, our result is intriguing because it shows that there is no FPRAS at (x,y)=(1-q/(1+epsilon),-epsilon) for any positive epsilon but it leaves open the limit point epsilon=0, which corresponds to approximately counting q-colourings of a planar graph.

Affiliated with

Also associated with

No associations

Rating

Inapproximability of the Tutte polynomial of a planar graph 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 of a planar graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inapproximability of the Tutte polynomial of a planar graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163979