Fixed-parameter tractable computation of Reshetikhin--Turaev knot polynomials via tensor networks

We give a thorough analysis of the time complexity of computing Reshetikhin–Turaev knot polynomials via tensor contractions on the associated tensor networks, showing that the computation is fixed-parameter tractable with respect to a parameter at most linear in the tree-width of the input knot diagram. When combined with existing approximation algorithms for tree decomposition, this recovers the sub-exponential bound $e^{O(\sqrt{n})}$ for the time complexity of computing any Reshetikhin–Turaev knot polynomial. We accompany this paper with an implementation of such an algorithm in SnapPy, which computes any Reshetikhin–Turaev knot polynomial given its $R$-matrix and ribbon element.