Black hole search
A black hole destroys every agent that enters it, without trace; a team must locate it, losing as few agents as possible.
Problem statement and measuresexpand
A connected graph contains one black hole: a node that destroys any agent arriving there, leaving no trace. All other nodes are safe. Agents start at a safe node \(s\) (the home base) and must determine the location of the black hole; at least one agent must survive and know it. The primary measure is the team size (number of agents needed); the secondary measure is the cost (total number of moves, a move being one traversal of one edge) or, for synchronous agents, the time. In most settings the black hole is present from the start; an eventually emerging black hole appears at an unknown time during the execution, and time is then counted from its appearance. Some papers also start the agents scattered, at distinct safe nodes; those results are recorded in the notes, because every catalogued variant starts at a home base.
Measures: Agents, number of agents needed (team size); Cost, total moves (asynchronous) or rounds (synchronous).
Dynamic graphs with whiteboards
verifiedIn an arbitrary dynamic graph from which at most one edge is missing per round, six co-located synchronous agents with whiteboards locate the black hole in \(O(m^2)\) rounds, and three are not enough.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: connected every round
- \(\mathcal G=(G_t)_{t\ge0}\) is 1-interval connected if every snapshot \(G_t=(V,E_t)\) is connected. More generally it is \(T\)-interval connected if for every \(t\) the graph \(\bigl(V,\bigcap_{i=t}^{t+T-1}E_i\bigr)\) is connected.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Faults: no faults
- All agents follow the algorithm forever.
- Black hole appearance: present from the start
- The black hole is present at time 0, and the home base \(s\) is safe throughout.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Knowledge of the graph: topology unknown
- Agents know \(n\) but not the topology of \(G\).
- Marking nodes: whiteboards
- Every node has a whiteboard that agents read and write under mutual exclusion.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
Statement for this variant
The graph is the footprint \(G\) (with \(n\) nodes and \(m\) edges) of a dynamic graph that is connected in every round; the results below assume in addition that at most \(\mu\) edges are missing in each round, mostly \(\mu = 1\). An agent at node \(v\) sees \(\deg(v)\) in \(G\) but not which incident edges are missing, and learns that an edge is missing only when its attempt to cross it fails. Agents are synchronous, have distinct identifiers, read the memory of the agents at the same node, and every node has a whiteboard. The black hole is located when an agent terminates at a safe node next to it and outputs the port that leads to it.
What is known
- Theorem 4.1 with \(\mu = 1\): three agents co-located at a safe node of \(K_3\), one node of which is the black hole, fail
- holds even with unbounded agent memory and unbounded whiteboards
- agents that know neither \(n\) nor \(\mu\) and learn that an edge is missing only by failing to cross it
- with up to \(\mu\) missing edges per round, \(2\mu+1\) co-located agents fail
Results, in order of publication
Introductory and current best (Theorem 6.3 of arXiv v2). Theorem 3.3 gives nine agents in the same time; Kaur et al. 2026a and Bileski & Miller 2026 cite this nine-agent algorithm from the ICDCN 2025 version.
Open questions
With at most one missing edge per round, do four or five co-located agents suffice? Three do not Kaur et al. 2026b.
With scattered agents and at most one missing edge per round, do \(2\deg(v_{BH})+1\) or \(2\deg(v_{BH})+2\) agents suffice? \(2\deg(v_{BH})\) do not Kaur et al. 2026b and \(2\deg(v_{BH})+3\) do Bileski & Miller 2026.
With up to \(\mu\) missing edges per round, can \(O(\mu)\) co-located agents locate the black hole in polynomial time? The known algorithm with \(6\mu\) agents takes exponential time Kaur et al. 2026b.
Notes
Checked against the full texts of Kaur et al. 2026b (arXiv v2), Kaur et al. 2026a (arXiv v2) and Bileski & Miller 2026 (arXiv v1). The three papers share the model: nodes are anonymous, ports are local, an agent at node \(v\) sees \(\deg(v)\) in the footprint \(G\) but not which incident edges are missing, and learns that an edge was missing only when its move fails; Kaur, Saxena, Mandal and Mondal contrast this with the dynamic rings, cactuses and tori of earlier work, where an agent sees which incident edge is missing Kaur et al. 2026b. Co-located agents read each other's memory. Kaur et al. first give nine co-located agents in \(O(m^2)\) rounds (Theorem 3.3) and then six (Theorem 6.3), both with \(O(\log n)\) bits per agent and per whiteboard Kaur et al. 2026b. With at most \(\mu\) missing edges per round (their \(f\) is \(\mu\) here), \(2\mu+1\) co-located agents fail even with unbounded memory and whiteboards (Theorem 4.1), and \(6\mu\) agents succeed in exponential time (Theorem 5.2) Kaur et al. 2026b.
Scattered agents (every agent starts at an arbitrary safe node; several agents may share a node), with \(\mu = 1\) and \(O(\log n)\) bits per agent and per whiteboard: \(2\deg(v_{BH})\) agents cannot solve the problem (Theorem 2.1 of Kaur et al. 2026b), where \(\deg(v_{BH})\) is the degree of the black hole in \(G\). Kaur, Saxena, Mandal and Mondal solve it with \(2\deg(v_{BH})+17\) agents in \(O(m^2)\) rounds (Theorem 2.2 of Kaur et al. 2026a, the extended version of Kaur et al. 2025): every agent runs a depth-first search and crosses each new edge by a cautious walk of its own, writing its outgoing port on the whiteboard before leaving and erasing it after coming back; two marks for the same port reveal the black hole, so at most \(2\deg(v_{BH})\) agents die, and a group of nine agents that meets switches to the algorithm for co-located agents. Bileski and Miller drop the switch: all agents run one exploration in which at most two agents wait at a missing edge, so once \(2\deg(v_{BH})\) agents have died a survivor reaches a revealing mark; \(2\deg(v_{BH})+3\) agents suffice in \(O(m^2\deg(v_{BH}))\) rounds (Theorem 1 of Bileski & Miller 2026, a preprint that gives proof sketches and defers the full proofs to a journal version). For rings with pebbles see the setting for dynamic rings.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.