Algorithms and complexity for Turaev-Viro invariants

DOI10.1007/978-3-662-47672-7_23MaRDI QIDQ3448792zbMATHOpenAlexFDO

Authors Clément Maria, Jonathan Spreer, Benjamin A. Burton

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Triangulating manifolds (57Q15) Parameterized complexity, tractability and kernelization (68Q27) Invariants of 3-manifolds (including skein modules, character varieties) (57K31)

Abstract: The Turaev-Viro invariants are a powerful family of topological invariants for distinguishing between different 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them require exponential time. The invariants are parameterised by an integer $rgeq3$. We resolve the question of complexity for $r=3$ and $r=4$, giving simple proofs that computing Turaev-Viro invariants for $r=3$ is polynomial time, but for $r=4$ is #P-hard. Moreover, we give an explicit fixed-parameter tractable algorithm for arbitrary $r$, and show through concrete implementation and experimentation that this algorithm is practical---and indeed preferable---to the prior state of the art for real computation.

Recommendations

• Algorithms and complexity for Turaev-Viro invariants
• Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants
• A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
• A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
• Computing Turaev-Viro invariants for 3-manifolds

Cites work

• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• scientific article; zbMATH DE number 2227021 (Why is no real title available?)
• Algorithmic topology and classification of 3-manifolds
• Computing Turaev-Viro invariants for 3-manifolds
• Courcelle's theorem for triangulations
• Detecting genus in vertex links for the fast enumeration of \(3\)-manifold triangulations
• Graph minors. II. Algorithmic aspects of tree-width
• Notes on Perelman's papers
• PP is as Hard as the Polynomial-Time Hierarchy
• STRUCTURES OF SMALL CLOSED NON-ORIENTABLE 3-MANIFOLD TRIANGULATIONS
• State sum invariants of 3-manifolds and quantum \(6j\)-symbols
• Symmetries, Isometries and Length Spectra of Closed Hyperbolic Three-Manifolds
• The 3-manifold invariants of Witten and Reshetikhin-Turaev for sl\((2,\mathbb{C})\)
• The complexity of computing the permanent
• Treewidth computations. I: Upper bounds
• Treewidth. Computations and approximations

Cited in

(9)

• Violator spaces: Structure and algorithms
• Algorithms and complexity for Turaev-Viro invariants
• A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
• Clarkson's algorithm for violator spaces
• Treewidth, crushing and hyperbolic volume
• Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants
• A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• scientific article; zbMATH DE number 7236450 (Why is no real title available?)

Describes a project that uses

Uses Software

• Regina
• ComputeTW
• LibTW

This page was built for publication: Algorithms and complexity for Turaev-Viro invariants

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