Computing Heegaard genus is NP-hard

2016/06/05 by Bachman, David, Derby-Talbot, Ryan, Sedgwick, Eric
#57M99 #57N10 #68Q17 #FOS: Mathematics #Geometric Topology (math.GT)

paper · doi:10.48550/arxiv.1606.01553

Abstract

We show that \sc Heegaard Genus ≤ 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 ≤ g.

Related

• Effective computation of the Heegaard genus of 3-manifolds
• Effective Computation of the Heegaard Genus of 3-Manifolds
• Comparing Heegaard and JSJ structures of orientable 3-manifolds
• Invariant Heegaard Surfaces in Manifolds with Involutions and the Heegaard Genus of Double Covers
• Heegaard genus and complexity of fibered knots