Geodesic
On the complexity of immersed normal surfaces
Burton, Benjamin1 ; Colin de Verdière, Éric2 ; de Mesmay, Arnaud3
1 School of Mathematics and Physics, The University of Queensland, Brisbane QLD 4072, Australia
2 Département d’informatique, École normale supérieure, CNRS, 45 rue d’Ulm, 75005 Paris, France
3 CNRS, GIPSA-lab, 11 rue des Mathématiques, Grenoble Campus BP46, F-38402 Saint Martin-d’Hères, France
Geometry & topology, Tome 20 (2016) no. 2, pp. 1061-1083.

Voir la notice de l'article provenant de la source Mathematical Sciences Publishers

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.

DOI : 10.2140/gt.2016.20.1061
Classification : 57N10, 68Q17, 57Q35, 68U05
Keywords: low-dimensional topology, normal surface, immersed normal surface, constraint satisfaction problem, three-manifold, computational complexity

Burton, Benjamin 1 ; Colin de Verdière, Éric 2 ; de Mesmay, Arnaud 3

1 School of Mathematics and Physics, The University of Queensland, Brisbane QLD 4072, Australia
2 Département d’informatique, École normale supérieure, CNRS, 45 rue d’Ulm, 75005 Paris, France
3 CNRS, GIPSA-lab, 11 rue des Mathématiques, Grenoble Campus BP46, F-38402 Saint Martin-d’Hères, France 
@article{GT_2016_20_2_a5,
     author = {Burton, Benjamin and Colin de Verdi\`ere, \'Eric and de Mesmay, Arnaud},
     title = {On the complexity of immersed normal surfaces},
     journal = {Geometry & topology},
     pages = {1061--1083},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2016},
     doi = {10.2140/gt.2016.20.1061},
     url = {http://geodesic.mathdoc.fr/articles/10.2140/gt.2016.20.1061/}
}
TY  - JOUR
AU  - Burton, Benjamin
AU  - Colin de Verdière, Éric
AU  - de Mesmay, Arnaud
TI  - On the complexity of immersed normal surfaces
JO  - Geometry & topology
PY  - 2016
SP  - 1061
EP  - 1083
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.2140/gt.2016.20.1061/
DO  - 10.2140/gt.2016.20.1061
ID  - GT_2016_20_2_a5
ER  - 
%0 Journal Article
%A Burton, Benjamin
%A Colin de Verdière, Éric
%A de Mesmay, Arnaud
%T On the complexity of immersed normal surfaces
%J Geometry & topology
%D 2016
%P 1061-1083
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.2140/gt.2016.20.1061/
%R 10.2140/gt.2016.20.1061
%F GT_2016_20_2_a5
Burton, Benjamin; Colin de Verdière, Éric; de Mesmay, Arnaud. On the complexity of immersed normal surfaces. Geometry & topology, Tome 20 (2016) no. 2, pp. 1061-1083. doi : 10.2140/gt.2016.20.1061. http://geodesic.mathdoc.fr/articles/10.2140/gt.2016.20.1061/

[1] I Agol, J Hass, W Thurston, The computational complexity of knot genus and spanning area, Trans. Amer. Math. Soc. 358 (2006) 3821

[2] I R Aitchison, S Matsumoto, J H Rubinstein, Surfaces in the figure-8 knot complement, J. Knot Theory Ramifications 7 (1998) 1005

[3] S Arora, B Barak, Computational complexity: a modern approach, Cambridge Univ. Press (2009)

[4] B A Burton, T Lewiner, J Paixão, J Spreer, Parameterized complexity of discrete Morse theory, from: "Computational geometry", Association for Computing Machinery (2013) 127

[5] B A Burton, J Spreer, The complexity of detecting taut angle structures on triangulations, from: "Proceedings of the 24th Annual ACM–SIAM Symposium on Discrete Algorithms", Society for Industrial and Applied Mathematics (2012) 168

[6] É Colin De Verdière, Topological algorithms for graphs on surfaces, Habilitation thesis, École normale supérieure (2012)

[7] N Creignou, S Khanna, M Sudan, Complexity classifications of Boolean constraint satisfaction problems, Society for Industrial and Applied Mathematics (2001)

[8] V Dalmau, D K Ford, Generalized satisfiability with limited occurrences per variable: a study through delta-matroid parity, from: "Mathematical foundations of computer science" (editors B Rovan, P Vojtáš), Lecture Notes in Comput. Sci. 2747, Springer (2003) 358

[9] T Feder, Fanout limitations on constraint systems, Theoret. Comput. Sci. 255 (2001) 281

[10] M R Fellows, Parameterized complexity: new developments and research frontiers, from: "Aspects of complexity" (editors R Downey, D Hirschfeldt), de Gruyter Ser. Log. Appl. 4, de Gruyter (2001) 51

[11] C Gordon, The theory of normal surfaces, lecture notes (2001)

[12] W Haken, Theorie der Normalflächen, Acta Math. 105 (1961) 245

[13] J Hass, J C Lagarias, N Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999) 185

[14] A Hatcher, Notes on basic 3–manifold topology, (2007)

[15] G Kuperberg, Knottedness is in NP, modulo GRH, Adv. Math. 256 (2014) 493

[16] D M Letscher, Immersed normal surfaces and decision problems for 3–manifolds, PhD thesis, University of Michigan (1997)

[17] J Matoušek, B Gärtner, Understanding and using linear programming, Springer (2007)

[18] S Matsumoto, R Rannard, The regular projective solution space of the figure-eight knot complement, Experiment. Math. 9 (2000) 221

[19] E E Moise, Affine structures in 3–manifolds, V : The triangulation theorem and Hauptvermutung, Ann. of Math. 56 (1952) 96

[20] R Rannard, Computing immersed normal surfaces in the figure-eight knot complement, Experiment. Math. 8 (1999) 73

[21] T J Schaefer, The complexity of satisfiability problems, from: "Tenth Annual ACM Symposium on Theory of Computing", ACM (1978) 216

[22] A Schrijver, Combinatorial optimization : polyhedra and efficiency, Volume A, 24, Springer (2003)

[23] J Stillwell, Classical topology and combinatorial group theory, 72, Springer (1993)

Cité par Sources :