The Complexity of Computing the Sign of the Tutte Polynomial
The Complexity of Computing the Sign of the Tutte Polynomial
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 …