I am interested into computational complexity of decision problem: Does a given 2-dimensional simplicial complex contain (any)triangulation of 2-sphere? This problem trivially lies into NP, because certificate is the subset of triangles. I think that it is NP-complete.
6
-
$\begingroup$ For those of us who are simplicial-simpletons, could you explain how you verify the certificate in polynomial time? $\endgroup$– Joel David HamkinsJan 8, 2013 at 15:18
-
$\begingroup$ If we are given set of triangles as a certificate, first we will check connectivity, afterwards we check that the link of each vertex is a cycle. If these conditions are satisfied, we know for sure that we have a closed surface. Then calculate Euler characteristic, we are dealing with sphere if and only if Euler characteristic is 2. en.wikipedia.org/wiki/Surface#Classification_of_closed_surfaces here you can check what are the Euler characteristics of closed surfaces. $\endgroup$– kakiaJan 8, 2013 at 15:32
-
$\begingroup$ Thanks very much! Would it be possible to give an example of the kind of difficult case you imagine? Or even merely a non-completely-trivial case, where a decision is made because of some global feature, rather than merely a local one---if all decisions are local, I expect it in P. Given a simplicial complex, we can reduce to its connected components, and we can seem to retract any boundaries, right? What kind of complexes are we left with? I apologize for my naive questions, but I find the topic interesting, and as I am currently the sole up-voter, I feel free to inquire. $\endgroup$– Joel David HamkinsJan 8, 2013 at 22:13
-
$\begingroup$ Ah, good, I see now that I am joined by other up-voters... $\endgroup$– Joel David HamkinsJan 8, 2013 at 22:21
-
2$\begingroup$ Complexes to worry about are something like Bing's "house with two rooms" which is a 2-dimensional complex which is contractible but not collapsible. In particular, "Bing's house" contains no embedded 2-spheres, but has no "boundaries" to retract. Of course, you can detect absence of 2-spheres by looking at 2-nd homology, but this example shows that one needs further global considerations. $\endgroup$– MishaJan 8, 2013 at 23:28
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
It is NP-complete. Here is a reduction from the graph 3-coloring problem.
For a given graph, consider a sphere with $n$ holes where $n$ is the number of vertices. Enumerate the holes by the vertices of the graph. Fill each hole by 3 discs (red, green and blue) by identifying each disc boundary with the hole boundary. Glue the centers of the 3 discs into one point (so that nor two of them cannot be included in one surface), Then, for every edge of the graph, pick one new point in each of the 6 discs filling the holes corresponding to the edge endpoints, and glue together each of the 3 pairs of chosen points lying on discs of the same color. The points chosen for different edges must be distinct.
The resulting topological space is homeomorphic to a simplicial complex (which is easy to construct from the graph in polynomial time). It contains a sphere if and only if the original graph is 3-colorable.
Remark. You can alter the formulation by saying that an immersed sphere which self-intersects itself in finitely many points is still a sphere. For this problem, the construction can be modified as follows. To make a pair of discs "forbidden", glue together two pairs of small discs in them rather than one pair of point. This creates a surface of positive genus if you try to pick a pair of discs connected this way.
answered Jan 9, 2013 at 8:58
-
$\begingroup$ In your construction, wouldn't two discs filling the same hole form a 2-sphere already? $\endgroup$ Jan 9, 2013 at 9:19
-
$\begingroup$ I see. This likely works, though I admit I couldn't tell how to prove that the complex can't accidentally contain a sphere. Interesting. $\endgroup$ Jan 9, 2013 at 13:29