Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Bläser, Markus; Hoffmann, Christian https://www.dagstuhl.de/lipics License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-13378
URL:

;

On the Complexity of the Interlace Polynomial

pdf-format:


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
Seminar: 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