Computing Heegaard Genus is NP-Hard

David Bachman (), Ryan Derby-Talbot () and Eric Sedgwick ()
Additional contact information
David Bachman: Pitzer College
Ryan Derby-Talbot: Quest University
Eric Sedgwick: DePaul University, School of Computing

A chapter in A Journey Through Discrete Mathematics, 2017, pp 59-87 from Springer

Abstract: Abstract We show that 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 CNF-SAT to Heegaard Genus ≤ g.

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-44479-6_3

Ordering information: This item can be ordered from
http://www.springer.com/9783319444796

DOI: 10.1007/978-3-319-44479-6_3

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().