Parameterized complexity of quantum invariants

Publication date 1 October 2019

Planar graphs; geometric and topological aspects of graph theory (05C10) Analysis of algorithms and problem complexity (68Q25)

Abstract: We give a general fixed parameter tractable algorithm to compute quantum invariants of links presented by diagrams, whose complexity is singly exponential in the carving-width (or the tree-width) of the diagram. In particular, we get a

O (N^{f r a c 32 m a t h r m c w} m a t h r m p o l y (n))

time algorithm to compute any Reshetikhin-Turaev invariant---derived from a simple Lie algebra

m a t h f r a k g

---of a link presented by a planar diagram with

n

crossings and carving-width

m a t h r m c w

, and whose components are coloured with

m a t h f r a k g

-modules of dimension at most

N

. For example, this includes the

N^{t h}

coloured Jones polynomials and the

N^{t h}

coloured HOMFLYPT polynomials.

This page was built for publication: Parameterized complexity of quantum invariants

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