A swarm of robots can mimic the behavior of biological swarms, like a swarm of social insects. In the freeze tag problem, there is one member of the swarm, a sentinel, whose task is to awaken the sleeping members of the swarm to respond to the stimulus noticed by the sentinel. The problem is to discover the dynamics and constraints governing the wakening process. In the scenario, the sentinel travels to a dormant member to awaken it. This creates a chain reaction in which both alert members of the swarm alert additional members of the swarm until they are all alert.

The problem is complicated by the need to make choices depending on distance and population density of members of the swarm. Does an alert member of the swarm go to the nearest neighbor first, or travel to a more distant location where there may be more sleepers clustered together?

The paper begins with a thorough review of previous and related work. The analysis of the problem and proofs begins with star graphs in the second section. The problem is shown to be nondeterministic polynomial-time (NP) hard, has an approximation lower bound of five over three, and a worst-case greedy algorithm bound of seven over three. When there is a star graph with the same number of robots on each leaf, the authors show that there is a polynomial-time approximation scheme. The third section extends the proofs to general graphs. Likewise, this problem is NP-hard, with five over three as the limit on the hardness approximation. The fourth section is on geometric spaces using a Euclidean distance metric. This section emphasizes the analysis of algorithms, and arrives at the conclusion that there is a polynomial-time approximation scheme for a geometric space. A running time estimate is also found. The fifth section is the shortest, and lists seven unsolved problems, in addition to the conjectures presented in earlier sections as challenges for further research. The emphasis on unsolved problems is an unusual feature. The paper is a significant contribution to the literature on swarm behavior and algorithms.