The HOMFLY-PT polynomial is fixed-parameter tractable

DOI10.4230/LIPICS.SOCG.2018.18MaRDI QIDQ5115785zbMATH OpenOpenAlexFDO

Authors Benjamin A. Burton

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1712.05776

zbMATH Keywords

knot invariantsknot theoryparameterised complexity

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Knot polynomials (57K14)

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.

Recommendations

• The parametrized complexity of knot polynomials
• On the computational complexity of the Jones and Tutte polynomials
• scientific article; zbMATH DE number 1305557
• A polynomial time knot polynomial
• scientific article; zbMATH DE number 475580

Cites work

• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 4049098 (Why is no real title available?)
• scientific article; zbMATH DE number 1092415 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A new polynomial invariant of knots and links
• A polynomial invariant for knots via von Neumann algebras
• Calculating the 2-variable polynomial for knots presented as closed braids
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Computing HOMFLY polynomials of 2-bridge links from 4-plat representation
• Introducing Regina, The 3-Manifold Topology Software
• Invariants of links of Conway type
• On the colored Tutte polynomial of a graph of bounded treewidth
• On the computational complexity of the Jones and Tutte polynomials
• Parameterized algorithms
• State models for link polynomials
• The first coefficient of Homflypt and Kauffman polynomials: Vertigan proof of polynomial complexity using dynamic programming
• The parametrized complexity of knot polynomials
• Treewidth. Computations and approximations

Cited in

(3)

• Using the HOMFLYPT polynomial to compute knot types
• On the pathwidth of hyperbolic 3-manifolds
• The parametrized complexity of knot polynomials

Describes a project that uses

Uses Software

• Regina

This page was built for publication: The HOMFLY-PT polynomial is fixed-parameter tractable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115785)