Bläser, Markus ;
Hoffmann, Christian
On the Complexity of the Interlace Polynomial
Abstract
We consider the twovariable interlace polynomial introduced by
Arratia, Bollob`as and Sorkin (2004). We develop two graph
transformations which allow us to derive pointtopoint 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 #Phard
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
twovariable interlace polynomial, the vertexnullity interlace
polynomial, the vertexrank interlace polynomial and the
independent set polynomial, are almost everywhere #Phard 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$.
BibTeX  Entry
@InProceedings{blser_et_al:LIPIcs:2008:1337,
author = {Markus Bl{\"a}ser and Christian Hoffmann},
title = {{On the Complexity of the Interlace Polynomial}},
booktitle = {25th International Symposium on Theoretical Aspects of Computer Science},
pages = {97108},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897064},
ISSN = {18688969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1337},
URN = {urn:nbn:de:0030drops13378},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1337},
annote = {Keywords: Computational complexity, approximation, interlace polynomial, independent set polynomial, graph transformation}
}
2008
Keywords: 

Computational complexity, approximation, interlace polynomial, independent set polynomial, graph transformation 
Seminar: 

25th International Symposium on Theoretical Aspects of Computer Science

Related Scholarly Article: 


Issue date: 

2008 
Date of publication: 

2008 