On the complexity of immersed normal surfaces

DOI10.2140/GT.2016.20.1061zbMATH Open1339.68258OpenAlexW2170715356MaRDI QIDQ280918FDOQ280918

Authors Éric Colin de Verdière, Arnaud de Mesmay, Benjamin A. Burton 

Publication date 10 May 2016

Published in Geometry \& Topology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.4988

zbMATH Keywords

computational complexitypolynomial-time algorithmBoolean constraint satisfactioncomputational 3-manifold theorylow-dimensional topologynormal surface

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Embeddings and immersions in PL-topology (57Q35)

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.

Recommendations

• The complexity of the normal surface solution space
• Finding non-orientable surfaces in 3-manifolds
• Finding non-orientable surfaces in 3-manifolds
• Computational topology and normal surfaces: theoretical and experimental complexity bounds
• Computing Immersed Normal Surfaces in the Figure-Eight Knot Complement

Cited In (6)

• Computing Heegaard genus is NP-hard
• Computational topology and normal surfaces: theoretical and experimental complexity bounds
• The complexity of the normal surface solution space
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• Computing Immersed Normal Surfaces in the Figure-Eight Knot Complement
• Some conditionally hard problems on links and 3-manifolds

This page was built for publication: On the complexity of immersed normal surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q280918)