1 Search Results for "Hoffmann, Christian"

Document
DOI: 10.4230/LIPIcs.STACS.2008.1337
On the Complexity of the Interlace Polynomial

Authors: Markus Bläser and Christian Hoffmann

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

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

Markus Bläser and Christian Hoffmann. On the Complexity of the Interlace Polynomial. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 97-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.STACS.2008.1337,
  author =	{Bl\"{a}ser, Markus and Hoffmann, Christian},
  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 =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.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}
}
  • Refine by Author
  • 1 Bläser, Markus
  • 1 Hoffmann, Christian

  • Refine by Classification

  • Refine by Keyword
  • 1 Computational complexity
  • 1 approximation
  • 1 graph transformation
  • 1 independent set polynomial
  • 1 interlace polynomial

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2008

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact