Inapproximability of the Tutte polynomial
| dc.creator | Goldberg, Leslie Ann | |
| dc.creator | Jerrum, Mark | |
| dc.date | 2006-05-30 | |
| dc.date | 2007-07-30 | |
| dc.date.accessioned | 2026-07-07T09:51:12Z | |
| dc.date.available | 2026-07-07T09:51:12Z | |
| dc.description | 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. | |
| dc.description | Minor changes to correct typos and provide clarification. Also includes an extra figure | |
| dc.identifier | https://arxiv.org/abs/cs/0605140 | |
| dc.identifier | http://arxiv.org/abs/cs/0605140 | |
| dc.identifier | Infomation and Computation 206(7), 908-929 (July 2008) | |
| dc.identifier | doi:10.1016/j.ic.2008.04.003 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/165205 | |
| dc.subject | Computational Complexity | |
| dc.subject | Combinatorics | |
| dc.title | Inapproximability of the Tutte polynomial | |
| dc.type | text |