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).
Eventually emerging black hole, synchronous agents, oriented ring
verifiedIf the black hole may appear at any time, even at the home base after the first round, three synchronous agents are necessary and sufficient on an oriented ring, and they find it within \(4n\) rounds of its appearance.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- 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: eventually emerging
- There is a time \(t \ge 0\) and a node \(u\) such that from time \(t\) on \(u\) destroys every agent on it or entering it, and stays a black hole. If \(t = 0\) then \(u \ne s\); the home base may become the black hole after the first round (after one epoch for asynchronous agents). Time is counted from \(t\) Bonnet et al. 2026b.
- 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: sense of direction
- Agents have a consistent sense of direction: a globally consistent labelling of edges from which they can tell whether two walks lead to the same node.
- Marking nodes: no marking
- Agents cannot leave information at nodes.
- Topology: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
Statement for this variant
The black hole appears at an unknown round and node (at the home base only after round 0) and stays. Agents have distinct identifiers, unbounded memory and face-to-face communication, and the ring is oriented. Time is counted from the appearance of the black hole.
What is known
- two agents may be together only at the home base, or one appearance destroys both; one agent then cannot tell whether the other died at distance 1 or at distance 2 from the home base (Theorem 1)
- a ring of \(n \ge 5\) nodes
- holds even with a safe home base, whiteboards, knowledge of \(n\) and implicit termination
Results, in order of publication
Introductory and current best (Algorithm A3, Theorem 4): at most \(4n\) rounds after the appearance. Without knowing \(n\), three agents need \(O(n^2)\) rounds (Algorithm A4, Theorem 5); three agents with one pebble need \(4n\) rounds (Algorithm A2, Theorem 3); four agents need \(3n\) rounds, as two pairs that never meet, each performing a cautious walk (Algorithm A1, Theorem 2).
Open questions
Is one algorithm optimal in every respect at once: three agents, no knowledge of \(n\), no pebble and \(O(n)\) rounds? Left open by Bonnet et al. 2026b.
Notes
Bonnet, Bramas and Lamani. Since the home base may become the black hole, it is not a safe meeting point, and agents that gather anywhere risk being destroyed together. Checked against the full text of Bonnet et al. 2026b (SAND 2026), which omits some proofs and pseudo-code for space.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.