Computing Heegaard genus is NP-hard
classification
🧮 math.GT
keywords
genusheegaardnp-hardproblemadmitscnf-satcomputingdeciding
read the original abstract
We show that {\sc Heegaard Genus $\leq g$}, 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 $\leq g$}.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.