When Agents are Powerful: Black Hole Search with Verification in Time-Varying Graphs

A black hole is a harmful node in a graph that destroys any agent entering it, making its identification a critical task. In the \emph{Black Hole Search with Verification (BHSV)} problem, a team of agents operates on a graph $G$ with the objective that at least one agent survives and correctly identifies an edge incident to the black hole; if no black hole exists, then all agents must terminate. Prior work has studied BHS in arbitrary dynamic graphs under the restrictive \emph{face-to-face} communication model, where agents can exchange information only when co-located. This constraint significantly increases the number of agents required to solve the problem. In this work, we strengthen the capabilities of agents by equipping them with (i) \emph{1-hop visibility}, (ii) \emph{global communication}, and (iii) both \emph{1-hop visibility} and \emph{global communication}. We show that these enhancements lead to more efficient solutions for the BHSV problem in dynamic graphs.