标题： 冻结标签在二维空间中使用$L_1$距离时是 NP 难的 显示英文标题

标题： Freeze-Tag is NP-hard in 2D with $L_1$ distance

摘要： 冻结-标签问题（FTP）是一个调度问题，应用于机器人群激活，并由Arkin等人于2002年提出。 这个问题寻求一种有效的方法，从一个活跃的机器人开始激活机器人群。 激活通过直接接触发生，一旦机器人变得活跃，它就可以移动并帮助激活其他机器人。 尽管该问题已被证明在欧几里得平面上$R^2$在$L_2$距离下是NP难的，并且在三维欧几里得空间$R^3$在任何$L_p$距离下且$p \ge 1$时是NP难的，但在$L_1$（曼哈顿）距离下$R^2$的复杂性仍然是一个开放问题。 在本文中，我们通过证明在欧几里得平面上使用$L_1$距离时 FTP 是强 NP-难的，解决了这个问题。 显示英文摘要

摘要： 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 $R^2$ under the $L_2$ distance, and in three-dimensional Euclidean space $R^3$ under any $L_p$ distance with $p \ge 1$, its complexity under the $L_1$ (Manhattan) distance in $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.