The complexity of pinning simple multiloops

Abstract

A multiloop with $s\in \mathbb{N}$ strands is a generic immersion ${\hat{I}}^3:{\bigsqcup }_1^s{\mathbb{S}}^1\looparrowright \hat{I}\pounds$ of the union of $s$ circles into a surface $\hat{I}\pounds$, considered up to homeomorphisms. A pinning set of ${\hat{I}}^3$ is a set of points $P\subset \hat{I}\pounds \setminus \mathrm{im}({\hat{I}}^3)$, such that in the punctured surface $\hat{I}\pounds \setminus P$, the immersion ${\hat{I}}^3$ has the minimal number of double points in its homotopy class. Its pinning number $\varpi ({\hat{I}}^3)$ is the minimum cardinal of its pinning sets. In any fixed orientable surface $\hat{I}\pounds$, the pinning problem which given a multiloop ${\hat{I}}^3$ and $k\in \mathbb{N}$ decides whether $\varpi ({\hat{I}}^3)\le k$ has been show to be NP-complete, even in restrictions to loops (with $s=1$ strand). In this work we study the complexity of the pinning problem in restriction to multiloops whose strands are simple (embedded circles). We show that in any fixed oriented surface $\hat{I}\pounds$, the problem is in P when $s\le 3$ and NP-complete when $s\ge 20$, and present some follow-up questions and conjectures.

33 pages, 22 figures