The complexity of pinning simple multiloops
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912887143923712 |
|---|---|
| author | Seo, Eric Simon, Christopher-Lloyd Stucky, Ben |
| author_facet | Seo, Eric Simon, Christopher-Lloyd Stucky, Ben |
| contents | A multiloop with $s\in \mathbb{N}$ strands is a generic immersion $γ\colon \sqcup_1^s \mathbb{S}^1 \looparrowright Σ$ of the union of $s$ circles into a surface $Σ$, considered up to homeomorphisms. A pinning set of $γ$ is a set of points $P\subset Σ\setminus \operatorname{im}(γ)$, such that in the punctured surface $Σ\setminus P$, the immersion $γ$ has the minimal number of double points in its homotopy class. Its pinning number $\varpi(γ)$ is the minimum cardinal of its pinning sets. In any fixed orientable surface $Σ$, the pinning problem which given a multiloop $γ$ and $k\in \mathbb{N}$ decides whether $\varpi(γ)\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 $Σ$, the problem is in P when $s\leq 3$ and NP-complete when $s\geq 20$, and present some follow-up questions and conjectures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07344 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The complexity of pinning simple multiloops Seo, Eric Simon, Christopher-Lloyd Stucky, Ben Geometric Topology Combinatorics 57K20 (Primary) 68Q25, 68U05 (Secondary) A multiloop with $s\in \mathbb{N}$ strands is a generic immersion $γ\colon \sqcup_1^s \mathbb{S}^1 \looparrowright Σ$ of the union of $s$ circles into a surface $Σ$, considered up to homeomorphisms. A pinning set of $γ$ is a set of points $P\subset Σ\setminus \operatorname{im}(γ)$, such that in the punctured surface $Σ\setminus P$, the immersion $γ$ has the minimal number of double points in its homotopy class. Its pinning number $\varpi(γ)$ is the minimum cardinal of its pinning sets. In any fixed orientable surface $Σ$, the pinning problem which given a multiloop $γ$ and $k\in \mathbb{N}$ decides whether $\varpi(γ)\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 $Σ$, the problem is in P when $s\leq 3$ and NP-complete when $s\geq 20$, and present some follow-up questions and conjectures. |
| title | The complexity of pinning simple multiloops |
| topic | Geometric Topology Combinatorics 57K20 (Primary) 68Q25, 68U05 (Secondary) |
| url | https://arxiv.org/abs/2602.07344 |