The Taub Faculty of Computer Science Events and Talks

The complexity of several prominent graph polynomials, such as the chromatic polynomial and the matching polynomial, has been studied in the literature. In 2008 Makowsky raised a conjecture which generalizes complexity results for specific graph polynomials to an infinite class of graph polynomials which include almost all of those in the literature. The conjecture states roughly that the evaluations of such graph polynomials are equivalent in terms of running-time complexity, except for a small and nicely structured exception set. As a case study for the conjecture, we consider a graph polynomial which originated in statistical mechanics in order to study phase transitions. A trivariate Ising polynomial was studied with respect to its approximability by L. A. Goldberg, M. Jerrum and M. Paterson in 2003. A related bivariate Ising polynomial was studied in by D. Andr\'{e}n and K. Markstr\"{o}m in 2009. We show that both Ising polynomials satisfy versions of Makowsky's conjecture, even when the domain is restricted. Under a counting version of the Exponential Time Hypothesis we give a dichotomy theorem stating that evaluations of the bivariate Ising polynomial either require exponential time runnning-time, or can be computed in polynomial time.