Searching for a Black Hole in a Dynamic Cactus

Abstract

In this paper, we study the problem of black hole search by a team of mobile agents. A black hole is a dangerous stationary node in a graph that eliminates any visiting agent without leaving any trace of its existence. Key parameters that dictate the complexity of finding the black hole include the number of agents required to locate the black hole, the number of moves performed by the agents and the time taken to determine the black hole location. This problem was first investigated in the context of dynamic rings by Di Luna et al. (Proc. of ICDCS 2021, IEEE, pp. 987-997). In this paper, we extend the same problem to a dynamic cactus. We introduce two categories of dynamicity. Firstly, we examine the scenario where the underlying graph has at most one dynamic edge, i.e., at most, one edge can disappear or reappear at any round. Secondly, we consider the problem for at most $k$ dynamic edges. In both cases, the underlying graph must be connected irrespective of which edge (or edges) is dynamic. Now for each case of dynamicities, we establish lower and upper bounds on the number of agents, moves and rounds required to locate the black hole.