Freeze-Tag Remains NP-hard on Binary and Ternary Trees
Resumo
The Freeze-Tag Problem (FTP) is a scheduling-like problem motivated by robot swarm activation. The input consists of the locations of a set of mobile robots in some metric space. One robot is initially active, while the others are initially frozen. Active robots can move at unit speed, and upon reaching the location of a frozen robot, the latter is activated. The goal is to activate all the robots within the minimum time, i.e., minimizing the time the last frozen robot is activated, the so-called makespan of the schedule. Arkin et al. proved that FTP is strongly NP-hard even if we restrict the problem to metric spaces arising from the metric closure of an edge-weighted star graph, where a frozen robot is placed on each leaf, and the active robot is placed at the center of this star [Arkin et al. 2002]. In this work, we continue to explore the complexity of FTP and show that it keeps its hardness even if further restricted to binary unweighted rooted trees with frozen robots only at leaves and the active robot on its root. Additionally, we prove that a generalized version, whose domain includes ternary weighted trees, remains hard, even if we require that every non-root node has precisely one frozen robot.
Referências
Arkin, E. M., Bender, M. A., Fekete, S. P., Mitchell, J. S. B., and Skutella, M. (2002). The Freeze-Tag Problem: How to Wake up a Swarm of Robots. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 568–577. Society for Industrial and Applied Mathematics.
Arkin, E. M., Bender, M. A., Fekete, S. P., Mitchell, J. S. B., and Skutella, M. (2006). The Freeze-Tag Problem: How to Wake Up a Swarm of Robots. Algorithmica, 46(2):193–221.
Arkin, E. M., Bender, M. A., and Ge, D. (2003). Improved Approximation Algorithms for the Freeze-Tag Problem. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 295–303. Association for Computing Machinery.
Brunner, J. and Wellman, J. (2019). An Optimal Algorithm for Online Freeze-Tag. In Farach-Colton, M., Prencipe, G., and Uehara, R., editors, 10th International Conference on Fun with Algorithms (FUN 2021), volume 157 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:11. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
Demaine, E. D. and Rudoy, M. (2017). Freeze Tag is Hard in 3D. In Abstracts from the 27th Fall Workshop on Computational Geometry, pages 108–110.
Hammar, M., Nilsson, B. J., and Persson, M. (2006). The online freeze-tag problem. In LATIN 2006: Theoretical Informatics, pages 569–579. Springer Berlin Heidelberg.
