Name
Title | ||
|---|---|---|
A polynomial time algorithm to compute quantum invariants 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 dimension of the first homology group of the manifold 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 extremely large family of 3-manifolds with first homology group of bounded rank. 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 roughly 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, Betti numbers, etc.) that can be computed ad-hoc when first investigating an unknown triangulation. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1137/1.9781611974782.180 | symposium on discrete algorithms |
Keywords | DocType | Volume |
fixed parameter tractable algorithms, Turaev-Viro invariants, triangulations of 3-manifolds, (integral) homology, almost normal surfaces, combinatorial algorithms | Conference | abs/1607.02218 |
ISBN | Citations | PageRank |
978-1-61197-503-1 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Clément Maria | 1 | 40 | 5.29 |
| Jonathan Spreer | 2 | 47 | 11.46 |