Freeze-Tag is Strongly NP-hard in 2D with $L_p$ Distances

Abstract

The Freeze-Tag Problem (FTP) asks for the minimum time needed to activate a swarm of robots, starting from a single active robot. When an active robot reaches a frozen robot, the latter becomes active; both robots may then move independently and activate further robots. We prove that FTP is strongly NP-hard in the plane under every fixed rational $L_p$ distance, $1 \le p < \infty$, and under $L_\infty$. The geometric argument also applies to every fixed real $p > 1$ for which the metric admits an effective specification. For $L_1$ and $L_\infty$, the integer-coordinate decision problems are strongly NP-complete. The reduction starts from Numerical 3-Dimensional Matching with distinct integers and also yields NP-completeness for unweighted planar grid graphs.