On the Complexity of Immersed Normal Surfaces

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.

17 pages, under journal submission

References in corpus (3)

• Parameterized Complexity of Discrete Morse Theory
• Knottedness is in NP, modulo GRH
• The complexity of detecting taut angle structures on triangulations

Cited by in corpus (1)

• Deciding contractibility of a non-simple curve on the boundary of a 3-manifold: A computational Loop Theorem