Don't Be Afraid to Die: Black Hole Search in Dynamic Graphs with Fewer Agents

The black hole search problem is a fundamental challenge in distributed computing on networks. A team of synchronous mobile agents operates in a port-labeled network where one node, the black hole, permanently destroys any agent that visits it. The goal is for at least one agent to survive, terminate at a node adjacent to the black hole, and output the port number leading to the black hole. Prior work by Kaur et al. (SSS 2025) established that $2{\delta }_{BH}+17$ agents suffice for this task in a 1-bounded 1-interval connected dynamic graph, where ${\delta }_{BH}$ is the degree of the black hole. A lower bound of $2{\delta }_{BH}+1$ was also shown by Kaur et al. (ICDCN 2025). This paper narrows the gap by proving that $2{\delta }_{BH}+3$ agents are sufficient, bringing the upper bound close to the lower bound.

The authors consider a team of synchronous mobile agents in a port-labeled network modeled as a 1-bounded 1-interval connected dynamic graph. In such graphs, the topology can change at each time step, but the graph remains connected at every interval, and the number of changes is bounded. The agents are initially scattered across the network. The algorithm designed by the authors coordinates the agents' movements to explore the network while avoiding the black hole. Key to the approach is a strategy that uses fewer agents by carefully managing the exploration and ensuring that at least one agent survives to report the black hole's location. The algorithm is analyzed to show that with $2{\delta }_{BH}+3$ agents, the task is solvable. The methodology involves a detailed case analysis and construction of agent trajectories that guarantee termination and correctness.