Parameterized Algorithms for the Freeze-Tag Problem over Different Domains

• Grant number: 22/13435-4
• Support Opportunities: Scholarships in Brazil - Master
• Start date: March 01, 2023
• End date: January 31, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Lehilton Lelis Chaves Pedrosa
• Grantee: Lucas de Oliveira Silva
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated scholarship(s): 23/12529-8 - Algorithms for the freeze-tag and related swarm robotics problems, BE.EP.MS

Abstract

Robot activation problems arise naturally in the context of swarm robotics. In particular, the Freeze-Tag Problem (FTP) consists of activating a set of "asleep" robots from just one initially active one by moving to the dormant robots' location. Once a robot is awake, it can assist in awakening other robots. The objective is to find a strategy to activate the entire set in the shortest possible time, i.e., that minimizes the makespan.This problem is NP-hard and has already been extensively explored from the perspective of approximation algorithms or meta-heuristics. Both in the geometric case and in the one where the input is a graph. However, few works in the literature deal with FTP from the perspective of parameterized algorithms.There are no polynomial algorithms for an NP-hard problem in the hypothesis that P does not equal NP. Therefore, the motivation for studying parameterized algorithms is that the instances considered in practice often have some fixed parameter (e.g., the maximum degree of the graph). This fact suggests looking for algorithms whose running time is a polynomial multiplied by a function that depends only on the parameter. We say the problem is Fixed-Parameter Tractable (FPT) when this is possible, that is, polynomial when such parameters are limited. This project aims to determine some parameters for which the Freeze-Tag Problem is FPT.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

CHAVES PEDROSA, LEHILTON LELIS; SILVA, LUCAS DE OLIVEIRA. Freeze-Tag is NP-hard in 3D with L₁ distance. XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, v. 224, p. 7-pg., 2023-01-01. (22/13435-4)