DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.43

Freeze-Tag with Return

Authors: Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Gabriel Le Bouder, Taïssir Marcé, and Nils Morawietz

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

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√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.

Cite as

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Gabriel Le Bouder, Taïssir Marcé, and Nils Morawietz. Freeze-Tag with Return. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bonichon_et_al:LIPIcs.MFCS.2026.43,
  author =	{Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Le Bouder, Gabriel and Marc\'{e}, Ta\"{i}ssir and Morawietz, Nils},
  title =	{{Freeze-Tag with Return}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.43},
  URN =		{urn:nbn:de:0030-drops-274241},
  doi =		{10.4230/LIPIcs.MFCS.2026.43},
  annote =	{Keywords: Freeze-Tag Problem, sleeping robots, metric spaces}
}

Search Results

Documents authored by Marcé, Taïssir

Freeze-Tag with Return

Abstract

Cite as

Thanks for your feedback!

Could not send message