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

摘要

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 γ. (Relative to the classical (x,y) parameterisation, q=(x−1)(y−1) and γ=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 γ=0. The situation for q=2 is different. Previous results for graphs imply inapproximability in the region −2⩽γ<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 γ<−2 unless NP=RP, and (ii) in the region γ>0, the approximation problem is hard for the complexity class #RHΠ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 #RHΠ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 #RHΠ1 under AP-reducibility, partially resolving a question that we first posed in 1992.