Black Hole Search in Dynamic Cactus Graph

We study the problem of black hole search by a set of mobile agents, where the underlying graph is a dynamic cactus. A black hole is a dangerous vertex in the graph that eliminates any visiting agent without leaving any trace behind. Key parameters that dictate the complexity of finding the black hole include: the number of agents required (termed as size), the number of moves performed by the agents in order to determine the black hole location (termed as move) and the time (or round) taken to terminate. This problem has already been studied where the underlying graph is a dynamic ring [6]. In this paper, we extend the same problem to a dynamic cactus. We introduce two categories of dynamicity, but still, the underlying graph needs to be connected: first, we examine the scenario where, at most, one dynamic edge can disappear or reappear at any round. Secondly, we consider the problem for at most k dynamic edges. In both scenarios, we establish lower and upper bounds for the necessary number of agents, moves and rounds.