Computing Heegaard genus is NP-hard

DOI10.1007/978-3-319-44479-6_3MaRDI QIDQ4604369zbMATH OpenOpenAlexFDO

Authors David Bachman, Ryan Derby-Talbot, 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 complexityNP-hardsatisfiability3-manifoldsHeegaard genus

Mathematics Subject Classification ID

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

Abstract: We show that {sc Heegaard Genus $leqg$}, the problem of deciding whether a triangulated 3-manifold admits a Heegaard splitting of genus less than or equal to $g$, is NP-hard. The result follows from a quadratic time reduction of the NP-complete problem {sc CNF-SAT} to {sc Heegaard Genus $leqg$}.

Recommendations

• The computational complexity of knot genus and spanning area
• Finding non-orientable surfaces in 3-manifolds
• Some conditionally hard problems on links and 3-manifolds
• Embeddability in \(R^3\) is NP-hard
• Sphere recognition lies in NP

Cites work

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

Cited in

(6)

• On the classification of Heegaard splittings
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• The computational complexity of knot genus and spanning area
• Finding non-orientable surfaces in 3-manifolds
• The computational complexity of knot genus in a fixed 3‐manifold
• Finding non-orientable surfaces in 3-manifolds

This page was built for publication: Computing Heegaard genus is NP-hard

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