The complexity of detecting taut angle structures on triangulations

DOI10.1137/1.9781611973105.13MaRDI QIDQ5741721zbMATH OpenOpenAlexFDO

Authors Jonathan Spreer, Benjamin A. Burton

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Relations of low-dimensional topology with graph theory (57M15) General geometric structures on low-dimensional manifolds (57M50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: There are many fundamental algorithmic problems on triangulated 3-manifolds whose complexities are unknown. Here we study the problem of finding a taut angle structure on a 3-manifold triangulation, whose existence has implications for both the geometry and combinatorics of the triangulation. We prove that detecting taut angle structures is NP-complete, but also fixed-parameter tractable in the treewidth of the face pairing graph of the triangulation. These results have deeper implications: the core techniques can serve as a launching point for approaching decision problems such as unknot recognition and prime decomposition of 3-manifolds.

Recommendations

• The computational complexity of basic decision problems in 3-dimensional topology
• Sphere recognition lies in NP
• Fixed parameter tractable algorithms in combinatorial topology
• scientific article; zbMATH DE number 7647903
• Finding non-orientable surfaces in 3-manifolds

Cited in

(9)

• Explicit angle structures for veering triangulations
• Some conditionally hard problems on links and 3-manifolds
• Courcelle's theorem for triangulations
• Computing Heegaard genus is NP-hard
• 3-manifold triangulations with small treewidth
• scientific article; zbMATH DE number 7236450 (Why is no real title available?)
• On the pathwidth of hyperbolic 3-manifolds
• On the width of complicated JSJ decompositions
• On the twin-width of smooth manifolds

This page was built for publication: The complexity of detecting taut angle structures on triangulations

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