Splitting (complicated) surfaces is hard (Q934027)

The authors solve the optimization problem of finding the shortest simple cycle that separates an orientable surface (2-manifold with boundary) into two topologically non-trivial components. The cycle is a continuous map of the unit circle on the considered surface. Firstly, the proof that computing the shortest splitting cycle on a given surface is NP-hard is given and then the algorithm for computation of the shortest splitting cycle is described and its hardness is discussed. The authors also show that the shortest splitting problem is fixed-parameter tractable with respect to the genus and the number of boundary components of the surface. The problem of finding the shortest cycle that separates the surface into two surfaces of prescribed topology is considered, too.