Computing Heegaard Genus is NP-Hard
| Autor: | Eric Sedgwick, Ryan Derby-Talbot, David Bachman |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | A Journey Through Discrete Mathematics ISBN: 9783319444789 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|