On the complexity of immersed normal surfaces

Burton, Benjamin A., de Verdière, Éric Colin and de Mesmay, Arnaud (2016) On the complexity of immersed normal surfaces. Geometry and Topology, 20 2: 1061-1083. doi:10.2140/gt.2016.20.1061

Author Burton, Benjamin A.
de Verdière, Éric Colin
de Mesmay, Arnaud
Title On the complexity of immersed normal surfaces
Journal name Geometry and Topology   Check publisher's open access policy
ISSN 1364-0380
Publication date 2016
Year available 2016
Sub-type Article (original research)
DOI 10.2140/gt.2016.20.1061
Open Access Status Not Open Access
Volume 20
Issue 2
Start page 1061
End page 1083
Total pages 24
Place of publication Coventry, United Kingdom
Publisher Mathematical Sciences Publishers
Collection year 2017
Language eng
Abstract Normal surface theory, a tool to represent surfaces in a triangulated 3–manifold combinatorially, is ubiquitous in computational 3–manifold theory. In this paper, we investigate a relaxed notion of normal surfaces where we remove the quadrilateral conditions. This yields normal surfaces that are no longer embedded. We prove that it is NP-hard to decide whether such a surface is immersed. Our proof uses a reduction from Boolean constraint satisfaction problems where every variable appears in at most two clauses, using a classification theorem of Feder. We also investigate variants, and provide a polynomial-time algorithm to test for a local version of this problem.
Keyword Low-dimensional topology
Normal surface
Immersed normal surface
Constraint satisfaction problem
Computational complexity
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
HERDC Pre-Audit
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Mon, 09 May 2016, 20:38:11 EST by Dr Benjamin Burton on behalf of Mathematics