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. 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 rings
verifiedIn a 1-interval-connected ring three agents are necessary and sufficient; with pebbles they need \(\Theta(n^{1.5})\) moves.
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.
- 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: tokens
- Agents carry tokens (pebbles) they can place at nodes or on ports; tokens are identical and carry no other information.
- Topology: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
What is known
- fewer agents fail even when co-located with whiteboards and identifiers
- \(n\) must be known
- co-located agents, whiteboards
Results, in order of publication
Introductory and current best; with face-to-face communication or vision \(\Theta(n^2)\).
Open questions
None recorded for this variant.
Notes
The ring is oriented and each agent carries one pebble; \(n\) must be known Di Luna et al. 2025. With scattered agents (distinct arbitrary starting nodes) the cost rises to \(\Theta(n^2)\) with pebbles, and with only face-to-face communication or vision scattered agents cannot solve the problem Di Luna et al. 2025. For arbitrary dynamic graphs in which at most one edge is missing per round, six co-located agents with \(O(\log n)\)-bit whiteboards suffice in \(O(m^2)\) rounds, while \(2\deg(v_{BH})\) agents from an arbitrary configuration cannot Kaur et al. 2026; \(\deg(v_{BH})\) is the degree of the black hole.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.