On the Complexity of the Interlace Polynomial

Abstract

We consider the two-variable interlace polynomial introduced by
   Arratia, Bollob`as and Sorkin (2004).  We develop two graph
   transformations which allow us to derive point-to-point reductions
   for the interlace polynomial.  Exploiting these reductions we
   obtain new results concerning the computational complexity of
   evaluating the interlace polynomial at a fixed point.  Regarding
   exact evaluation, we prove that the interlace polynomial is #P-hard
   to evaluate at every point of the plane, except at one line, where
   it is trivially polynomial time computable, and four lines and two
   points, where the complexity mostly is still open.  This solves a
   problem posed by Arratia, Bollob`as and Sorkin (2004).  In
   particular, we observe that three specializations of the
   two-variable interlace polynomial, the vertex-nullity interlace
   polynomial, the vertex-rank interlace polynomial and the
   independent set polynomial, are almost everywhere #P-hard to
   evaluate, too.  For the independent set polynomial, our reductions
   allow us to prove that it is even hard to approximate at every
   point except at $-1$ and~$0$.