When Agents are Powerful: Black Hole Search with Verification in Time-Varying Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917365255503872 |
|---|---|
| author | Kaur, Tanvir Saxena, Ashish |
| author_facet | Kaur, Tanvir Saxena, Ashish |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_22309 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | When Agents are Powerful: Black Hole Search with Verification in Time-Varying Graphs Kaur, Tanvir Saxena, Ashish Distributed, Parallel, and Cluster Computing 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. |
| title | When Agents are Powerful: Black Hole Search with Verification in Time-Varying Graphs |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2510.22309 |