Computing Heegaard Genus is NP-Hard
From MaRDI portal
Publication:4604369
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
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) × S1
- 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