pith. sign in

arxiv: 2606.21985 · v1 · pith:D6OSJ4GXnew · submitted 2026-06-20 · 💻 cs.DS

Freeze-Tag with Return

Nicolas Bonichon , Cyril Gavoille , Nicolas Hanusse , Gabriel Le Bouder , Ta\"issir Marc\'e , Nils Morawietz This is my paper

Pith reviewed 2026-06-26 11:08 UTC · model grok-4.3

classification 💻 cs.DS
keywords Freeze-Tag Problemrobot awakeningmakespan minimizationreturn constraintunit diskNP-hardnessExponential Time Hypothesis
0
0 comments X

The pith

In the unit disk the makespan difference between standard robot awakening and awakening with return is bounded between 1.732 and 1.959.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the Freeze-Tag-with-Return Problem in which awake robots must return to their starting positions after waking all others. It establishes that when sleeping robots lie on the unit disk centered at the source, the optimal makespan for the return version exceeds the standard version by at most 1.959 and by at least 1.732 in the worst case. The work also proves an upper bound of 2 + 2√2 on the makespan when robots occupy convex positions and supplies single-exponential algorithms that are asymptotically tight under the Exponential Time Hypothesis for general distance functions.

Core claim

The central claim is that for n sleeping robots placed on the unit disk, the optimal makespan of the Freeze-Tag-with-Return Problem and the standard Freeze-Tag Problem differ by a constant independent of n: the difference is at most 1.959 for every instance and at least 1.732 for some instances; when the robots lie in convex position the makespan is at most 2 + 2√2, a bound attained by some configurations; single-exponential algorithms solve the problem exactly for arbitrary distance functions and are optimal under ETH because the problem remains NP-hard even on unweighted graphs.

What carries the argument

The bounded difference between optimal makespans of FTP and FTRP on the unit disk, proved via geometric comparison of awakening tours with and without return legs.

If this is right

  • The return constraint imposes only a constant overhead on awakening time regardless of the number of robots.
  • Some convex configurations force the makespan to reach exactly 2 + 2√2.
  • Exact solutions remain computable in single-exponential time for any fixed distance function.
  • No subexponential algorithm exists for the general problem unless the Exponential Time Hypothesis fails.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The constant gap implies that requiring robots to return home after a mission adds only a small fixed delay even as the swarm grows.
  • The unit-disk bounds may serve as a starting point for analyzing the same problems under other speed models or in higher dimensions.
  • The NP-hardness on graphs suggests that practical implementations for large swarms will need approximation or heuristic methods.

Load-bearing premise

All robots move at the same unit speed and every sleeping robot lies exactly on the unit disk centered at the source.

What would settle it

A concrete set of points on the unit disk whose optimal FTRP makespan minus optimal FTP makespan exceeds 1.959, or whose convex-position makespan exceeds 2 + 2√2.

read the original abstract

In the standard Freeze-Tag Problem (FTP), an initially awake robot (the source) is in charge of waking up a swarm of sleeping robots by moving towards them, given that all the awake robots can participate in the awakening process. The goal is to minimize the makespan to wake up all robots assuming they move at unit speed. In this paper we introduce the Freeze-Tag-with-Return Problem (FTRP) variant, where the robots must eventually return to their initial positions. In the Euclidean plane with $n$ sleeping robots lying on the unit disk centered at the initial position of the source, we show a non-trivial relationship between FTP and FTRP by proving that the difference between the optimal makespan of both problems never exceeds $1.959$, and is at least $1.732$ in the worst-case. We also present several upper and lower bounds on the optimal makespan. In particular, we show that if the sleeping robots are in convex positions, then the optimal makespan is at most $2 + 2\sqrt{2}$, which is achieved by some instances. From an algorithmic point-of-view, we present single-exponential algorithms for general distance functions. In metric spaces, these algorithms are asymptotically optimal under the ETH, which we show via an NP-hardness reduction on unweighted graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper introduces the Freeze-Tag-with-Return Problem (FTRP) variant of the Freeze-Tag Problem (FTP), in which awake robots must return to their initial positions after waking sleeping robots. For n sleeping robots on the unit disk in the Euclidean plane, it proves that the difference between the optimal FTP and FTRP makespans is at most 1.959 and at least 1.732 in the worst case. For convex positions it shows an upper bound of 2 + 2√2 on the optimal makespan (achieved by some instances). It also gives single-exponential algorithms for general distance functions that are asymptotically optimal under ETH via an NP-hardness reduction from unweighted graphs.

Significance. If the stated bounds hold, the work establishes a tight quantitative relationship between FTP and FTRP makespans under a natural geometric model and supplies matching upper/lower bounds for the convex case. The algorithmic contribution is strengthened by the explicit geometric arguments, case analysis, and linear-size parameterized reduction that yields ETH-tightness; these elements provide concrete, falsifiable predictions for robot-swarm coordination problems.

minor comments (1)
  1. [Abstract] The constant 1.959 is presented without an explicit derivation sketch in the abstract or introduction; a brief indication of the geometric optimization or case analysis that produces it would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, accurate summary of our contributions, and recommendation to accept. No major comments were raised that require addressing.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines a new problem variant FTRP and establishes its relationship to FTP via explicit geometric case analysis on the unit disk (difference bounds 1.959/1.732), convex-position upper bound 2+2√2, and single-exponential algorithms with ETH-tightness via linear-size NP-hardness reduction on unweighted graphs. No derivation step reduces by construction to a fitted parameter, self-definition, or self-citation chain; all central claims rest on independent constructions and external complexity assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; review is limited to the abstract so the ledger cannot be populated with concrete items.

pith-pipeline@v0.9.1-grok · 5785 in / 1190 out tokens · 33309 ms · 2026-06-26T11:08:16.810024+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references

  1. [1]

    The makespan is 2 ` 2 ?

    The smallest makespan achieved by a wake-up tree with only one leaf (and one return arc) corresponds to the circuitP0,P 1,P 2,P 3,P 0. The makespan is 2 ` 2 ?

  2. [2]

    The optimal wake-up tree for theFTP takes1 ` ? 3: one unit forr0 to reachr1 and ? 3 to wake upr2 and r3 in parallel.r0 (resp

    We can have a smaller makespan with a wake-up tree with two leaves. The optimal wake-up tree for theFTP takes1 ` ? 3: one unit forr0 to reachr1 and ? 3 to wake upr2 and r3 in parallel.r0 (resp. r1) returns to its initial position in time1(resp. ? 3). Thus we 14 Freeze-Tag with Return P0 P1 P3 P2 makespan: 4.464101615137754 P0 P1 P2 P3 P4 makespan: 4.82842...

  3. [3]

    We can not do better since the two awake robots reaching the two leaves have to return to different initial positions and one of them is at distance at least?

  4. [4]

    The first hop in the wake-up tree has length1whereas the second hop has necessary length ?

  5. [5]

    We show that the smallest makespan is achieved by a wake-up tree with only one leaf that takes a time2` 2 ?

    Ÿ ŹClaim 15.Forn“4,γ idp4q ěγap4q ě2`2 ? 2«4.824, Proof. We show that the smallest makespan is achieved by a wake-up tree with only one leaf that takes a time2` 2 ?

  6. [6]

    The unweighted depth is at least3

    Assume that we have two leaves in a wake-up tree with smallest makespan. The unweighted depth is at least3. Consider the root-leaf pathP0,Pi,Pj,Pk of a leafPk reached in3hops. The first hop P0,Pi has length1and the next two hops have length at least ? 2 since the pairwise distance between sleeping robots is at least ?

  7. [7]

    Thus the length of the trajectory of this robot is at least2`2 ? 2.Ÿ P1, P5

    The robot that moved toPk then has to return to an initial position, which is at a distance of at least1fromP k. Thus the length of the trajectory of this robot is at least2`2 ? 2.Ÿ P1, P5 . . . Pn P2 P3 P4 P0 P1, P5 . . . Pn P2 P3 P4 P0 P1, P5 . . . Pn P2 P3 P4 P0 P1, P5 . . . Pn P2 P3 P4 P0 Figure 7Positions are such these four wake-up trees are optimal...

  8. [8]

    We have =APiψpPiq “=P jPiψpPiq ´=P jPiA“ =PjPiPi´1 `=Pi´1PiψpPiq `=PjPiA“θ` π 2 ´ π 2 “θP r0,πs

    Since P is a convex point set,θP r0,πs. We have =APiψpPiq “=P jPiψpPiq ´=P jPiA“ =PjPiPi´1 `=Pi´1PiψpPiq `=PjPiA“θ` π 2 ´ π 2 “θP r0,πs. It turns out thatψpPjq is not in the same half-space bounded by the linepA,Piq containingPj. Similarly,ψpPjq is not in the half-space bounded by the parallel ofpA,Piq going throughPj containingPi. We then use the previou...

  9. [9]

    y´ 3{2x` 4sinpx{2q is ´3{2 ` 2 cospx{2q is equal to zero forx“x 0 “arccosp 3{4q

    The trajectory of the initial awake robotr0 can be represented by the sequence of five points pP0,P 1,P 2,Pj,P 0q. It makes at most4hops since it may happen thatP2 or Pj 4 That is a distribution of robots in the unit disk ofpR2,ℓ2q where the initial awake robot is at the origin. N. Bonichon, C. Gavoille, N. Hanusse, G. Le Bouder, T. Marcé, and N. Morawiet...

  10. [10]

    Recall thatαq “ 1 ` 2 ? 2` 2π{3 ´ 2 ? 3 is the angular distance fromP1 to Q, and thatr2 is awakened at time1` |P1P 2|

    For robots tr2,...,rj´1u lying on pP1,Qq. Recall thatαq “ 1 ` 2 ? 2` 2π{3 ´ 2 ? 3 is the angular distance fromP1 to Q, and thatr2 is awakened at time1` |P1P 2|. We get that the completion time is1` |P1P2| `t lpαq ´ |P1P2|,βq. From Lemma 21,tlpαq ´|P1P2|,βq ďαq ´|P1P2|´2π{3`2 ?

  11. [11]

    Hence the total completion time is at most1` |P1P2| `1`2 ? 2`2π{3´2 ? 3´ |P 1P2| ´2π{3`2 ? 3“2`2 ? 2

  12. [12]

    For robots trj,...,rku lying on the arcpQPkq. We upper bound the wake up time of rj by approximating the movement ofr0 as if it does a detour before waking uprj: we consider the geometric pathP0,P 1,P 2,Q,P j, that is longer than actualr0’s path. Then we upper bound the makespan ofpPj,Pkq by considering the makespan of the arcpQPkq as ifr 0 acts as the fi...

  13. [13]

    Its completion time is given by the sum of its wake-up time and the length of the pathP1,P 2,P 1

    Whenr1 wakes up (at time at most1), it goes toP2 and returns. Its completion time is given by the sum of its wake-up time and the length of the pathP1,P 2,P 1. It is upper bounded by1 ` 2chordpαq ď1 ` 2chordp2π{3q “ 1 ` 2 ?

  14. [14]

    Forn“ 4if points of P are in convex positions, the proof is a direct application of Theorem 2

    This conclude the proof forn“ 3 since other robotsr2 andr 3 stays still. Forn“ 4if points of P are in convex positions, the proof is a direct application of Theorem 2. Hence we only have to prove it for the non-convex distribution of sleeping robots. In fact we use AlgorithmConvexand provide the analysis for non-convex distribution when n“ 4. With four po...

  15. [15]

    r0’s path is thus P0,P 1,Pi,Pk,P 0

    If Pi is within the triangle pP0,P 1,Pkq, it is r0 that wakes upri. r0’s path is thus P0,P 1,Pi,Pk,P 0

  16. [16]

    Oncer1 wakes upri, it returns toP1 whiler i goes toPk`1 and returns

    If Pi is within the trianglepP0,P 1,Pk`1q, thenri’s awakening is attributed tor1. Oncer1 wakes upri, it returns toP1 whiler i goes toPk`1 and returns. We now provide the analysis of the strategy. In order to bound each paths’ length, we upper bound the distance between the subset of positions that are in a convex configuration by assuming these positions ...

  17. [17]

    We start by showing Item 1

    for each clausecPC , there is at least one literal ofc for which the corresponding vertex is inRand 2.for each variablex,Rcontains either vertexxor vertex x. We start by showing Item 1. 34 Freeze-Tag with Return Ź Claim 26.For each vertex vPL d, there is an ancestoru of v with uPL var`1 such that the robot onuwoken up at timevar`1. Proof.Recall that foriP...

  18. [18]

    Then, in order to wake-up all sleeping robots inX‰∅ , this robot has to select and go to some positionvPX

    If b“ 1, there is only one awake robot at positionu. Then, in order to wake-up all sleeping robots inX‰∅ , this robot has to select and go to some positionvPX . From that positionv, two awake robots are available to wake-up all remaining sleeping robots initially located at positions ofXz tvu, and the optimal makespan for this subtask is T2pv,Xz tvuq by d...

  19. [19]

    Ifb“ 2, there are two awake robots available at positionu. Then, in the optimal solution, one of the two robots atu has to wake-up the robots sleeping on a certain subsetA of positions inX, whereas the other robot atu has to wake-up the remaining robots sleeping on positions inXzA. Then, the makespan is the maximum of this two branches, and thus T2pu,Xq “...

  20. [20]

    Thus the first robot has to return to its initial positionr to complete its task

    It is clear thatTbpu,∅,rq “dpu,rq , for anybP t1,2u , since there are no other robots to wake-up. Thus the first robot has to return to its initial positionr to complete its task. The possible second awake robot atu has no moves to do in order to return to its initial position

  21. [21]

    Then, in order to complete its task, this robot has to select and go to some position vPX‰∅

    If b“ 1, only one robot is awake at positionu, which corresponds to its initial position. Then, in order to complete its task, this robot has to select and go to some position vPX‰∅ . From this position v, two awake robots have to wake-up all remaining sleeping robots inXz tvu, the first robotv having still to return to its initial positionr. The optimal ...

  22. [22]

    Then, in the optimal solution, the first one atu (whose return position isr) has to wake-up some subsetAĎX of sleeping robots

    If b“ 2, two awake robots are available at positionu. Then, in the optimal solution, the first one atu (whose return position isr) has to wake-up some subsetAĎX of sleeping robots. Subset A is possibly empty, allowing the robot to return directly to r thanks to the previous caseX“∅ . The second robot atu has to wake-up all the other sleeping robots, those...

  23. [23]

    It is clear in that case that theb awake robots atu have to return to a unique position ofR, since there are no other robots to wake-up

    If |X| “∅ , then we have|R| “b by assumption. It is clear in that case that theb awake robots atu have to return to a unique position ofR, since there are no other robots to wake-up. So,Tbpu,∅,Rq “max rPRdpu,rq, since one of theb return arcs must have this length

  24. [24]

    Then, in order to complete its task, this robot has to select and go to some positionvPX‰∅

    If b“ 1, only one robot is awake at positionu. Then, in order to complete its task, this robot has to select and go to some positionvPX‰∅ . From this position v, two awake robots have to wake-up all remaining sleeping robots inXz tvu, and also return to some unique position inR, including the initial awake robot atu. The optimal makespan for this subtask ...

  25. [25]

    Then, in the optimal solution, the first one atu has to wake-up some subsetAĎX of sleeping robots, and to select in R a return position, sayr1

    If b“ 2, two awake robots are available at positionu. Then, in the optimal solution, the first one atu has to wake-up some subsetAĎX of sleeping robots, and to select in R a return position, sayr1. Once awake, these robots whose initial positions were inA will have to select a unique position inRz tr1u, forming some subsetS1 of positions. Let S“S 1 Y tr1u...