Freeze-Tag is NP-hard in 3D with L1 distance

Abstract

The Freeze-Tag Problem (FTP) is the task of scheduling the activation of a robot swarm. The input consists of the initial locations of a set of mobile robots in some metric space. A single robot is initially “active” while the others are initially “frozen”. Active robots can move at unit speed, and upon reaching the location of a frozen robot, the latter is activated. The goal is to activate all the robots within the minimum time, minimizing the so-called makespan of the schedule. The complexity of this problem in Euclidean spaces was open until 2017, when Abel et al. [1] proved that FTP is NP-hard in the Euclidean plane with L2 distance. During that same year, Demaine and Rudoy [2] showed that it is also NP-hard in 3D Euclidean space with Lp distance for any p > 1, but left open the case with p = 1. This paper closes this gap and shows that FTP is indeed NP-hard in 3D Euclidean space with L1 distance. Furthermore, the hardness result holds in the strong sense, such that every coordinate is a rational bounded by a polynomial in the instance size.