On the Complexity of the Interlace Polynomial

Markus Bläser & Christian Hoffmann
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...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.