The Tutte polynomial: sign and approximability

5 November 2013
14:30
Mark Jerrum
Abstract
<p>The Tutte polynomial of a graph $G$ is a two-variable polynomial $T(G;x,y)$, which encodes much information about~$G$. The number of spanning trees in~$G$, the number of acyclic orientations of~$G$, and the partition function of the $q$-state Potts model are all specialisations of the Tutte polynomial. Jackson and Sokal have studied the sign of the Tutte polynomial, and identified regions in the $(x,y)$-plane where it is ``essentially determined'', in the sense that the sign is a function of very simple characteristics of $G$, e.g., the number of vertices and connected components of~$G$. It is natural to ask whether the sign of the Tutte polynomial is hard to compute outside of the regions where it is essentially determined. We show that the answer to this question is often an emphatic ``yes'': specifically, that determining the sign is \#P-hard. In such cases, approximating the Tutte polynomial with small relative error is also \#P-hard, since in particular the sign must be determined. In the other direction, we can ask whether the Tutte polynomial is easy to approximate in regions where the sign is essentially determined. The answer is not straightforward, but there is evidence that it often ``no''. This is joint work with Leslie Ann Goldberg (Oxford).</p>
  • Combinatorial Theory Seminar