Volume 20, issue 2 (2016)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 28
Issue 5, 1995–2482
Issue 4, 1501–1993
Issue 3, 1005–1499
Issue 2, 497–1003
Issue 1, 1–496

Volume 27, 9 issues

Volume 26, 8 issues

Volume 25, 7 issues

Volume 24, 7 issues

Volume 23, 7 issues

Volume 22, 7 issues

Volume 21, 6 issues

Volume 20, 6 issues

Volume 19, 6 issues

Volume 18, 5 issues

Volume 17, 5 issues

Volume 16, 4 issues

Volume 15, 4 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 5 issues

Volume 11, 4 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 3 issues

Volume 7, 2 issues

Volume 6, 2 issues

Volume 5, 2 issues

Volume 4, 1 issue

Volume 3, 1 issue

Volume 2, 1 issue

Volume 1, 1 issue

The Journal
About the Journal
Editorial Board
Editorial Procedure
Subscriptions
 
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
 
ISSN 1364-0380 (online)
ISSN 1465-3060 (print)
Author Index
To Appear
 
Other MSP Journals
On the complexity of immersed normal surfaces

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

Geometry & Topology 20 (2016) 1061–1083
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.

Keywords
low-dimensional topology, normal surface, immersed normal surface, constraint satisfaction problem, three-manifold, computational complexity
Mathematical Subject Classification 2010
Primary: 57N10, 68Q17
Secondary: 57Q35, 68U05
References
Publication
Received: 16 October 2014
Accepted: 28 June 2015
Published: 28 April 2016
Proposed: Cameron Gordon
Seconded: Dmitri Burago, Bruce Kleiner
Authors
Benjamin A Burton
School of Mathematics and Physics
The University of Queensland
Brisbane QLD 4072
Australia
http://www.maths.uq.edu.au/~bab/
Éric Colin de Verdière
Département d’informatique
École normale supérieure, CNRS
45 rue d’Ulm
75005 Paris
France
http://www.di.ens.fr/~colin/
Arnaud de Mesmay
CNRS
GIPSA-lab
11 rue des Mathématiques
Grenoble Campus BP46
F-38402 Saint Martin-d’Hères
France
http://www.gipsa-lab.fr/~arnaud.demesmay