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.

This version corrects the construction error that led to the withdrawal of the earlier manuscript