{"ID":2850314,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.22309","arxiv_id":"2510.22309","title":"When Agents are Powerful: Black Hole Search with Verification in Time-Varying Graphs","abstract":"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.","short_abstract":"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 incide...","url_abs":"https://arxiv.org/abs/2510.22309","url_pdf":"https://arxiv.org/pdf/2510.22309v2","authors":"[\"Tanvir Kaur\",\"Ashish Saxena\"]","published":"2025-10-25T14:21:39Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}