When Agents are Powerful: Black Hole Search with Verification in Time-Varying Graphs
For researchers in distributed computing and graph exploration, this work provides more efficient solutions to a fundamental problem in dynamic networks by relaxing communication constraints.
This paper studies the Black Hole Search with Verification problem in time-varying graphs, showing that equipping agents with 1-hop visibility and/or global communication reduces the required number of agents compared to the face-to-face model. For example, with both capabilities, only 2 agents suffice for 1-interval-connected graphs, whereas prior work required O(log n) agents.
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.