Efficient algorithms to decide tightness

Abstract

Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but more efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces. In this article, we present a new polynomial time procedure to decide tightness for triangulations of 3-manifolds - a problem which previously was thought to be hard. In addition, for the more difficult problem of deciding tightness of 4-dimensional combinatorial manifolds, we describe an algorithm that is fixed parameter tractable in the treewidth of the 1-skeletons of the vertex links. Finally, we show that simpler treewidth parameters are not viable: for all non-trivial inputs, we show that the treewidths of both the 1-skeleton and the dual graph must grow too quickly for a standard treewidth-based algorithm to remain tractable.