Paper Info
Title
A Polynomial-Time Algorithm To Compute Turaev-Viro Invariants Tv4,Q Of 3-Manifolds With Bounded First Betti Number
Abstract
In this article, we introduce a fixed-parameter tractable algorithm for computing the Turaev-Viro invariants TV4, q, using the first Betti number, i.e. the dimension of the first homology group of the manifold with Z(2)-coefficients, as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of TV4, q is known to be #P-hard in general; using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the family of 3-manifolds with first Z(2)-homology group of bounded dimension. Our algorithm is easy to implement, and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3-manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets, we are able to almost double the pairs of 3-manifolds we can distinguish. We hope this qualifies TV4, q to be added to the short list of standard properties (such as orientability, connectedness and Betti numbers) that can be computed ad hoc when first investigating an unknown triangulation.
Year
DOI
Venue
2020
10.1007/s10208-019-09438-8
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS
Keywords
DocType
Volume
Fixed-parameter tractable algorithms, Turaev-Viro invariants, Triangulations of 3-manifolds, (Integral)homology, (Generalised)normal surfaces, Discrete algorithms
Journal
20
Issue
ISSN
Citations 
5
1615-3375
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Clément Maria100.34
Jonathan Spreer24711.46