Computing Heegaard genus is NP-hard

DOI10.1007/978-3-319-44479-6_3zbMATH Open1388.57020arXiv1606.01553OpenAlexW2413157341MaRDI QIDQ4604369FDOQ4604369

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)

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$}.

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

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

zbMATH Keywords

computational complexityNP-hardsatisfiability3-manifoldsHeegaard genus

Mathematics Subject Classification ID

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

Cites Work

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