Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.14357 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917208909676544 |
|---|---|
| author | Silva, Lucas de Oliveira Pedrosa, Lehilton Lelis Chaves |
| author_facet | Silva, Lucas de Oliveira Pedrosa, Lehilton Lelis Chaves |
| contents | The Freeze-Tag Problem (FTP) is a scheduling problem with application in robot swarm activation and was introduced by Arkin et al. in 2002. This problem seeks an efficient way of activating a robot swarm, starting with a single active robot. Activations occur through direct contact, and once a robot becomes active, it can move and help activate other robots. Although the problem has been shown to be NP-hard in the Euclidean plane $\mathbb{R}^2$ under the $L_2$ distance, and in three-dimensional Euclidean space $\mathbb{R}^3$ under any $L_p$ distance with $p \ge 1$, its complexity under the $L_1$ (Manhattan) distance in $\mathbb{R}^2$ has remained an open question. In this paper, we settle this question by proving that FTP is strongly NP-hard in the Euclidean plane with $L_1$ distance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14357 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Freeze-Tag is NP-hard in 2D with $L_1$ distance Silva, Lucas de Oliveira Pedrosa, Lehilton Lelis Chaves Computational Geometry Computational Complexity The Freeze-Tag Problem (FTP) is a scheduling problem with application in robot swarm activation and was introduced by Arkin et al. in 2002. This problem seeks an efficient way of activating a robot swarm, starting with a single active robot. Activations occur through direct contact, and once a robot becomes active, it can move and help activate other robots. Although the problem has been shown to be NP-hard in the Euclidean plane $\mathbb{R}^2$ under the $L_2$ distance, and in three-dimensional Euclidean space $\mathbb{R}^3$ under any $L_p$ distance with $p \ge 1$, its complexity under the $L_1$ (Manhattan) distance in $\mathbb{R}^2$ has remained an open question. In this paper, we settle this question by proving that FTP is strongly NP-hard in the Euclidean plane with $L_1$ distance. |
| title | Freeze-Tag is NP-hard in 2D with $L_1$ distance |
| topic | Computational Geometry Computational Complexity |
| url | https://arxiv.org/abs/2509.14357 |