Computing Heegaard Genus is NP-Hard

DOI10.1007/978-3-319-44479-6_3zbMath1388.57020arXiv1606.01553MaRDI QIDQ4604369

Ryan Derby-Talbot, David Bachman, Eric Sedgwick

Publication date: 26 February 2018

Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexity; 3-manifolds; NP-hard; satisfiability; Heegaard genus

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Algorithms for contractibility of compressed curves on 3-manifold boundaries, Finding non-orientable surfaces in 3-manifolds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of immersed normal surfaces
• An algorithm to determine the Heegaard genus of a 3-manifold
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• Topological index theory for surfaces in 3-manifolds
• Heegaard surfaces and the distance of amalgamation
• Heegaard splittings of twisted torus knots
• Foliations and the topology of 3-manifolds. III
• Irreducible Heegaard splittings of Seifert fibered spaces are either vertical or horizontal
• Heegaard splittings of \((\text{surface})\times I\) are standard
• Heegaard structures of negatively curved 3-manifolds
• Integer homology 3-spheres admit irreducible representations in \(\mathrm{SL}(2,{\mathbb C})\)
• Persistence of Heegaard structures under Dehn filling
• Topology and combinatorics of 3-manifolds
• Decision problems in the space of Dehn fillings
• 0-efficient triangulations of 3-manifolds
• Thin position and the recognition problem for \(S^ 3\)
• Stabilizing and destabilizing Heegaard splittings of sufficiently complicated 3-manifolds
• Heegaard structures of manifolds in the Dehn filling space
• Some conditionally hard problems on links and 3-manifolds
• Knottedness is in NP, modulo GRH
• Sweepouts of amalgamated 3-manifolds
• The computational complexity of knot and link problems
• Embeddability in the 3-Sphere Is Decidable
• Heegaard surfaces in Haken 3-manifolds
• 3-manifold knot genus is NP-complete
• The Classification of Heegaard Splittings for (Compact Orient Able Surface) × S¹
• CLOSED ESSENTIAL SURFACES AND WEAKLY REDUCIBLE HEEGAARD SPLITTINGS IN MANIFOLDS WITH BOUNDARY
• Examples of tunnel number one knots which have the property ‘1 + 1 = 3’
• The Heegaard structure of Dehn filled manifolds
• The complexity of detecting taut angle structures on triangulations
• Finiteness results for Heegaard surfaces in surgered manifolds