Algorithms and Complexity for Turaev-Viro Invariants

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

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

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

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

Cited In (6)

• Treewidth, crushing and hyperbolic volume
• Violator spaces: Structure and algorithms
• Title not available (Why is that?)
• 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

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)