The HOMFLY-PT polynomial is fixed-parameter tractable

DOI10.4230/LIPICS.SOCG.2018.18zbMATH Open1494.68101arXiv1712.05776OpenAlexW2963742164MaRDI QIDQ5115785FDOQ5115785

Benjamin A. Burton

Publication date: 18 August 2020

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.

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

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

zbMATH Keywords

knot invariantsknot theoryparameterised complexity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• The parametrized complexity of knot polynomials
• On the pathwidth of hyperbolic 3-manifolds

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)