The Complexity of Computing the Sign of the Tutte Polynomial

Understand

We study the complexity of computing the sign of the Tutte polynomial of a graph.

• As there are only three possible outcomes (positive, negative, and zero), this seems at first sight more like a decision problem than a counting problem.
• Surprisingly, however, there are large regions of the parameter space for which computing the sign of the Tutte polynomial is actually #P-hard.
• As a trivial consequence, approximating the polynomial is also #P-hard in this case.