Pin the loop taut: a one-player topologame
Christopher-Lloyd Simon, Ben Stucky · Research Square · 2024
Abstract We introduce a 1-player game called pin the loop and analyse its complexity. A loop is a generic immersion of the circle in a surface, considered up to isotopy. A loop is taut when it is minimally intersecting in its homotopy class. A pinning set of a loop is a set of points P in the surface avoiding the loop, such that the loop is taut in the surface punctured at P. The pinning number is the minimal cardinal of its pinning sets, and a pinning set is optimal if it has that cardinal. We show that the decision problem associated to computing the pinning number of a plane loop is NP-complete. We implement a polynomial algorithm to check if a given point-set is pinning, adapting a method of Birman--Series for computing intersection numbers of curves in surfaces. After improving a theorem of Hass--Scott characterising taut loops in surfaces, we reduce the problem to a boolean formula whose solutions correspond to the pinning sets. Finally, we reduce the vertex-cover problem for graphs to an instance of the pinning problem for plane loops. Our results imply that given a closed geodesic in a complete Riemannian surface with punctures, it is hard to guess the location of the punctures from the sole isotopy class of the geodesic in the compactified surface.