2026-08-21T16:28:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27424 2026-08-21T14:42:39Z ddc:004 open_access

Freeze-Tag with Return Bonichon, Nicolas Gavoille, Cyril Hanusse, Nicolas Le Bouder, Gabriel Marcé, Taïssir Morawietz, Nils Freeze-Tag Problem sleeping robots metric spaces 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√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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Bonichon and Cyril Gavoille and Nicolas Hanusse and Gabriel Le Bouder and Taïssir Marcé and Nils Morawietz 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.43 urn:nbn:de:0030-drops-274241 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.43 eng https://creativecommons.org/licenses/by/4.0/legalcode