Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots

Definitions and mathematical statement

Let $p_0,\ldots,p_{n-1}$ be the initial robot locations in a metric space $(X,d)$, with only the robot at the designated source $p_0$ initially awake. Under the usual unit-speed convention, an awake robot can move between locations in time given by distance, and awakens a sleeping robot when they meet. The newly awakened robot may move and awaken others immediately. A schedule's makespan is the time when all robots are awake; write $t^*$ for the minimum achievable makespan.

The first question is whether computing an optimal schedule is NP-hard when the sites lie in ${\mathbb{R}}^2$ with Euclidean distance, or with $L_1$ distance $d(x,y)=|x_1-y_1|+|x_2-y_2|$. For a formal complexity claim, finite input encoding and the optimization or threshold-decision formulation must be fixed; NP-hardness does not assert membership in NP for exact Euclidean comparisons.

The second question is whether general finite metrics admit a polynomial-time approximation with a guarantee asymptotically better than $O(\log n)$: a schedule of length at most $\rho(n)t^*$ with, for example, $\rho(n)=o(\log n)$. The source does not state an exact improvement scale; a smaller constant in a logarithmic factor is a different target.

The source also describes an equivalent rooted spanning-tree problem, with maximum out-degree two and radius equal to the maximum sum of edge lengths along a root-to-vertex path. A scheduling convention is missing in that description: with only one initially awake robot, the source initially has only one active continuation, whereas awakening an ordinary vertex creates two. A usual awakening-tree representation therefore needs a root constraint or auxiliary-vertex convention, beyond an unrestricted binary branching root. The source's tree assertion is preserved with this qualification rather than used to redefine the physical scheduling problem.

Short English statement

Determine the planar hardness of optimally waking robots, and improve the general-metric logarithmic approximation ratio. The supplied report says planar hardness is settled while the approximation question remains separate.

Sources

• Local UnsolvedMath registry, permanent ID 5500035, exact source code catalogue entry, "Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots"; no proposer or year supplied. Registry status solved, classification SOLVED-IN-LITERATURE.
• The Open Problems Project, Problem 35, https://topp.openproblem.net/p35; public source specification https://github.com/edemaine/topp. Supplied source-TeX extraction accessed July 29, 2026. The maintained entry is reported as conjecturing Euclidean/$L_1$ planar NP-hardness and reporting NP-completeness for star metrics.
• The research summary says planar NP-hardness is established in Euclidean and $L_p$ planes, citing Yu et al. (2017) and a strong-NP-hardness result (2025), without precise publications or norm/parameter hypotheses. It explicitly leaves the general-metric improvement beyond the $O(\log n)$ approximation scale as a separate open question. These are supplied assessments, not independent literature verification.
• Rights note: the source repository LICENSE expressly covers software; reuse permission for problem text is flagged NEEDS_REVIEW. Public availability does not settle that scope.