Freeze-Tag is NP-hard in 3D with L₁ distance

Author(s)

Chaves Pedrosa, Lehilton Lelis ; Silva, Lucas de Oliveira

• Document type: Journal article
• Source: XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023; v. 224, p. 7-pg., 2023-01-01.

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 L-2 distance. During that same year, Demaine and Rudoy [2] showed that it is also NP-hard in 3D Euclidean space with L-p 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 L-1 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. (AU)

• FAPESP's process: 22/13435-4 - Parameterized Algorithms for the Freeze-Tag Problem over Different Domains
• Grantee: Lucas de Oliveira Silva
• Support Opportunities: Scholarships in Brazil - Master