The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex
Benjamin A. Burton, Sergio Cabello, Stefan Kratsch, William Pettersson · SIAM Journal on Discrete Mathematics · 2019
We consider the problem of finding a subcomplex $\mathcal{K}'$ of a simplicial complex $\mathcal{K}$ such that $\mathcal{K}'$ is homeomorphic to the 2-dimensional sphere, $\mathbb{S}^2$. We study two variants of this problem. The first asks if there exists such a $\mathcal{K}'$ with at most $\mathcal{K}$ triangles, and we show that this variant is ${\mathsf{W[1]}}$-hard and, assuming the exponential time hypothesis, admits no $n^{o(\sqrt{k})}$-time algorithm. We also give an algorithm that is tight with regard to this lower bound. The second problem is the dual of the first and asks if $\mathcal{K}'$ can be found by removing at most $k$ triangles from $\mathcal{K}$. This variant has an immediate $\mathcal{O}(3^{k}poly(|\mathcal{K}|))$-time algorithm, and we show that it admits a polynomial kernelization to $\mathcal{O}(k^2)$ triangles, as well as a polynomial compression to a weighted version with bit-size $\mathcal{O}(k \log k)$. This article has been changed.