computational complexity

2013-01-08T13:13:53Z

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.

Answer by Sergei Ivanov for computational complexity

2013-01-09T08:58:27Z

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.

computational complexity - MathOverflow

computational complexity

Answer by Sergei Ivanov for computational complexity