Algorithms and complexity for Turaev-Viro invariants

DOI10.1007/978-3-662-47672-7_23zbMATH Open1440.68112OpenAlexW2963051194MaRDI QIDQ3448792FDOQ3448792

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)

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

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)