Computing Heegaard genus is NP-hard

David Bachman, Ryan Derby-Talbot, Eric Sedgwick

We show that {\sc Heegaard Genus $\le 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. Th…