Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials

Details Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials

2010-06-27

arxiv.org/abs/1006.5234v2

Computer Science

Computational Complexity

Scientific paper

We consider the problem of approximating certain combinatorial polynomials. First, we consider the problem of approximating the Tutte polynomial of a binary matroid with parameters q>= 2 and gamma. (Relative to the classical (x,y) parameterisation, q=(x-1)(y-1) and gamma=y-1.) A graph is a special case of a binary matroid, so earlier work by the authors shows inapproximability (subject to certain complexity assumptions) for q>2, apart from the trivial case gamma=0. The situation for q=2 is different. Previous results for graphs imply inapproximability in the region -2<=gamma<0, apart from at two "special points" where the polynomial can be computed exactly in polynomial time. For binary matroids, we extend this result by showing (i) there is no FPRAS in the region gamma<-2 unless NP=RP, and (ii) in the region gamma>0, the approximation problem is hard for the complexity class #RHPi_1 under approximation-preserving (AP) reducibility. The latter result indicates a gap in approximation complexity at q=2: whereas an FPRAS is known in the graphical case, there can be none in the binary matroid case, unless there is an FPRAS for all of #RHPi_1. The result also implies that it is computationally difficult to approximate the weight enumerator of a binary linear code, apart from at the special weights at which the problem is exactly solvable in polynomial time. As a consequence, we show that approximating the cycle index polynomial of a permutation group is hard for #RHPi_1 under AP-reducibility, partially resolving a question that we first posed in 1992.

Affiliated with

Also associated with

No associations

Rating

Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials 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 Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-615648