Finding surfaces in simplicial complexes with bounded-treewidth 1-skeleton.
Mitchell Black, Amir Nayyeri · arXiv (Cornell University) · 2021
We consider the problem 2-Dim-Bounding-Surface. 2-Dim-Bounded-Surface asks whether or not there is a subcomplex $S$ of a simplicial complex $K$ homeomorphic to a given compact, connected surface bounded by a given subcomplex $B\subset K$. 2-Dim-Bounding-Surface is NP-hard. We show it is fixed-parameter tractable with respect to the treewidth of the 1-skeleton of the simplicial complex $K$. Using some of the techniques we developed for the 2-Dim-Bounded-Surface problem, we obtain fixed parameter tractable algorithms for other topological problems such as computing an optimal chain with a given boundary and computing an optimal chain in a given homology class.