10.4230/LIPICS.STACS.2008.1337
Bläser, Markus
Markus
Bläser
Hoffmann, Christian
Christian
Hoffmann
On the Complexity of the Interlace Polynomial
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Computational complexity
approximation
interlace polynomial
independent set polynomial
graph transformation
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13378
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
10
97
108
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
214665 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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$.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 97-108