2026-08-17T09:43:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8731 2024-03-06T10:42:31Z ddc:004 open_access

The HOMFLY-PT Polynomial is Fixed-Parameter Tractable Burton, Benjamin A. Knot theory knot invariants parameterised complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin A. Burton 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.18 urn:nbn:de:0030-drops-87311 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.18 eng https://creativecommons.org/licenses/by/3.0/legalcode