License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1337
URN: urn:nbn:de:0030-drops-13378
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1337/
Go to the corresponding LIPIcs Volume Portal

Bläser, Markus ; Hoffmann, Christian

On the Complexity of the Interlace Polynomial

pdf-format:
22011.BlaeserMarkus.Paper.1337.pdf (0.2 MB)

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$.

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 =	{97--108},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1337},
  URN =		{urn:nbn:de:0030-drops-13378},
  doi =		{10.4230/LIPIcs.STACS.2008.1337},
  annote =	{Keywords: Computational complexity, approximation, interlace polynomial, independent set polynomial, graph transformation}
}

Keywords: Computational complexity, approximation, interlace polynomial, independent set polynomial, graph transformation
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI