License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.18
URN: urn:nbn:de:0030-drops-87311
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8731/
Burton, Benjamin A.
The HOMFLY-PT Polynomial is Fixed-Parameter Tractable
Abstract
Many polynomial invariants of knots and links, including the Jones and HOMFLY-PT polynomials, are widely used in practice but #P-hard to compute. It was shown by Makowsky in 2001 that computing the Jones polynomial is fixed-parameter tractable in the treewidth of the link diagram, but the parameterised complexity of the more powerful HOMFLY-PT polynomial remained an open problem. Here we show that computing HOMFLY-PT is fixed-parameter tractable in the treewidth, and we give the first sub-exponential time algorithm to compute it for arbitrary links.
BibTeX - Entry
@InProceedings{burton:LIPIcs:2018:8731,
author = {Benjamin A. Burton},
title = {{The HOMFLY-PT Polynomial is Fixed-Parameter Tractable}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {18:1--18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8731},
URN = {urn:nbn:de:0030-drops-87311},
doi = {10.4230/LIPIcs.SoCG.2018.18},
annote = {Keywords: Knot theory, knot invariants, parameterised complexity}
}
|
Keywords: |
|
Knot theory, knot invariants, parameterised complexity |
|
Collection: |
|
34th International Symposium on Computational Geometry (SoCG 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.06.2018 |
