Mobility Matters
Home›Mobile agents on graphs›Exploration›Collaborative exploration›Black hole search

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 measurescollapse
black holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesABStart: agents A, B at s; ring of 6Cautious walk: mark the edge trying, cross, return, mark it safeA enters the black hole and is destroyed; B goes onB has explored its half; it walks to A's last safe edgeB reads 'trying' on edge v1-v2: the black hole is v2
Black hole search on a ring by two agents with cautious walk Dobrev et al. 2007 (the problem: Dobrev et al. 2006). Agents A and B start at the safe home base \(s\) of a ring of six nodes; one node (black) destroys every agent that enters it. Each explores half of the unexplored nodes: before crossing a new edge it marks it trying on the whiteboard (dashed), and after arriving it returns to mark it safe (green) before going on. A dies on its second new edge; B finishes its half, walks back through the explored part and finds the edge still marked trying: the one unexplored node beyond it is the black hole. One agent survives and knows it.

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).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine a computer network in which one computer has been taken over: every travelling program that arrives there is deleted without a trace, and nobody outside can tell. Find that computer by sending such programs, while losing as few of them as possible. We model the network as a graph: computers are nodes, cables between them are edges, and each travelling program is an agent. In the basic version the graph has \(n\) nodes and contains exactly one black hole, a node that destroys every agent that enters it; every other node is safe. A team of identical agents starts at a safe node \(s\), the home base; they have no map, but they know \(n\). At each node the edges leaving it are numbered \(1, 2, \dots\) (these numbers are called ports), each node has a whiteboard (a small memory on which agents can read and write notes), and the agents are asynchronous: every move (one traversal of one edge) takes a finite but unpredictable time, chosen by an adversary (an imagined opponent who picks the worst timing). The task: at least one agent must survive and know exactly which node is the black hole. We count the agents needed and the total number of moves.

1AlgorithmCautious walk and halving the unexplored ring Asynchronous agents with whiteboards in a ring → Dobrev et al. 2007

Two agents start together at \(s\) on a ring of \(n\) nodes (a cycle in which every node has two neighbours); they know \(n\).

  1. Cautious walk (used for every step into the unknown): an agent that crosses an edge nobody has crossed before first writes "I am trying this edge" on the whiteboard where it starts. If it arrives safely, it immediately goes back and changes the note to "this edge is safe", and only then continues. Nobody else ever enters an edge marked "trying".
  2. The unexplored nodes form one stretch of the ring. A phase starts: cut it into two halves of almost equal length; one agent explores the left half, the other the right half, both by cautious walk.
  3. The black hole lies in at most one half, so one agent finishes its half. It walks through the explored part to the last safe edge of the other agent.
  4. What is still unexplored is again one stretch, at most about half as long. A new phase starts: the finishing agent cuts it in two again, writes the new plan on the whiteboard there for its partner (in case the partner is only slow and comes back), and takes the half on the far side, away from the edge its partner is trying.
  5. When only one unexplored node remains, that node is the black hole.
Why it works and what it costs. Under cautious walk an agent that does not come back has died on the very first node beyond its last safe edge, so the black hole, if it has killed the partner, lies in the near half; the finishing agent always takes the far half and never enters an edge marked "trying", so exactly one agent dies and the other survives. Each phase at least halves the unexplored stretch, so there are about \(\log n\) phases, and each phase costs \(O(n)\) moves (walking around the explored part and exploring), giving \(O(n\log n)\) moves. Dobrev et al. 2007 show the exact cost \(2n\log n + O(n)\), and they prove that any algorithm, with any number of agents, needs at least \((n-1)\log(n-1) + O(n)\) moves, so this simple plan is optimal up to a factor of two.

Why it matters. Cautious walk is the basic safety tool of almost every later black hole search algorithm, in rings and in arbitrary graphs.

2Lower boundEvery unexplored port may lead to the black hole Asynchronous agents with whiteboards → Dobrev et al. 2006

Without a map, the agents do not know where a port leads. The adversary may therefore decide, as the algorithm runs, that the first port tried out of a node is the one that leads to the black hole. Take a graph in which the black hole is a neighbour of many nodes, for example the black hole \(0\) joined to every other node, with the home base at node \(1\). The first agent leaving node \(1\) through a new port is sent into the black hole. Some other agent must then reach node \(2\); the first agent that leaves node \(2\) through a new port is again sent into the black hole, and so on, node after node. Each such node costs one agent, and the search is not finished while two or more nodes are still unexplored, because a node that nobody has returned from may be the black hole or may simply be slow to reach.

Why it holds. In this example the algorithm loses an agent at almost every node adjacent to the black hole, and the black hole can have up to \(\Delta\) neighbours, where \(\Delta\) is the largest number of edges at any node (the maximum degree). With a cleverer graph (a ring of nodes all joined to a central black hole, which the adversary later replaces by a graph of maximum degree \(\Delta\) that looks the same to the agents) Dobrev et al. 2006 prove that \(\Delta + 1\) agents are needed; the full proof is longer. The same paper gives an algorithm with exactly \(\Delta + 1\) agents and \(O(n^2)\) moves, and shows that \(\Omega(n^2)\) moves are necessary for a team of this size, so both bounds are tight.

Why it matters. It shows that what limits a team without a map is the number of ports that can lead to the black hole, which is why a map or a sense of direction lowers the team to two agents.

3ImpossibilityWithout knowing \(n\), slow and dead look the same Asynchronous agents with whiteboards → Dobrev et al. 2006

Because moves take unpredictable time, an agent that has not come back may be dead or just slow. Suppose the agents do not know \(n\). Take a graph \(G\) with the black hole at node \(v\), and a second graph \(G'\) in which \(v\) is replaced by two nodes \(v_1\) and \(v_2\) joined to each other, sharing the edges that went to \(v\). In \(G'\) the adversary makes every edge into \(v_1\) or \(v_2\) extremely slow. Up to the moment the algorithm stops, the agents see exactly the same things in \(G\) and in \(G'\), so they stop in \(G'\) too, with both \(v_1\) and \(v_2\) unexplored: they cannot know which one is the black hole.

Why it holds. The same reasoning shows that the agents can never stop while two nodes are unexplored, and that the problem is unsolvable when the graph has a node (other than \(s\)) whose removal disconnects it: if that node is the black hole, everything behind it stays unexplored Dobrev et al. 2006. This is why the basic version assumes that \(n\) is known and that the graph stays connected after removing any one node (it is 2-connected).

Why it matters. The indistinguishability of slow and dead agents is the reason asynchronous black hole search needs knowledge of \(n\), and it reappears in every asynchronous lower bound for the problem.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Agents
Cost
Asynchronous agents with whiteboards standard
Without a map, \(\Delta+1\) asynchronous agents are necessary and sufficient, and they need \(\Theta(n^2)\) moves.
tight \(\Delta+1\) vs \(\Delta+1\) agents lost in the black hole
tight \(O(n^2)\) vs \(\Omega(n^2)\) asynchrony
Asynchronous agents with whiteboards in a ring
In an anonymous ring of known size, two co-located asynchronous agents are necessary and sufficient, at optimal cost \(\Theta(n\log n)\).
tight \(2\) vs \(2\) agents lost in the black hole
tight \(2n\log n+O(n)\) vs \(\Omega(n\log n)\) asynchrony
Whiteboards and a map
With a map, two agents locate the black hole in \(\Theta(n\log n)\) moves.
tight \(2\) vs \(2\) agents lost in the black hole
tight \(\Theta(n\log n)\) vs —
Tokens and a map
Whiteboards can be replaced by one pebble per agent: two agents, \(\Theta(n\log n)\) moves, even on non-FIFO edges.
tight \(2\) vs \(2\) agents lost in the black hole
tight \(\Theta(n\log n)\) vs —
Whiteboards and sense of direction
With sense of direction two agents suffice, still with \(\Theta(n^2)\) moves.
tight \(2\) vs \(2\) agents lost in the black hole
tight \(O(n^2)\) vs —
Tokens, no map
With a constant number of tokens and no map, \(\Delta+2\) agents and 3 tokens are necessary and sufficient.
tight \(\Delta+2\) vs \(\Delta+2\) agents lost in the black hole
polynomial gap \(O(mn)\) vs \(\Omega(n^2/\Delta)\) asynchrony
Synchronous agents with a map
With synchrony, two agents and a map, the question becomes the fastest exploration schedule, which is NP-hard to find.
tight \(2\) vs —
polynomial gap \(3\tfrac{3}{8}\text{-approx.}\) vs \(\text{NP-hard}\) combinatorial hardness
Eventually emerging black hole, synchronous agents, arbitrary graphs
On arbitrary graphs four co-located synchronous agents locate an eventually emerging black hole by moving in a cautious chain along a universal exploration sequence; whether three suffice is open.
tight \(4\) vs \(3\) agents lost in the black hole
unknown \(\mathrm{poly}(n)\) vs —
Eventually emerging black hole, synchronous agents, oriented ring
If 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.
tight \(3\) vs \(3\) agents lost in the black hole
unknown \(O(n)\) vs —
Eventually emerging black hole, asynchronous agents, oriented ring
With asynchronous agents no algorithm can announce the location of an eventually emerging black hole once and for all; with implicit termination, \(n\) agents that never communicate locate it within \(2n\) epochs.
polynomial gap \(n\) vs \(3\) agents lost in the black hole
unknown \(O(n)\) vs —
Byzantine companions, with a map
If up to \(f\) agents are Byzantine (they collude with the black hole and survive it), \(2f+2\) agents suffice with a map.
near-optimal \(2f+2\) vs —
unknown \(O(n+f)\) vs —
Byzantine companions, whiteboards, no map
Without a map but with whiteboards, \((f+1)(\Delta+1)\) agents locate the black hole in \(O(m+f)\) rounds.
near-optimal \((f+1)(\Delta+1)\) vs —
unknown \(O(m+f)\) vs —
Dynamic rings
In a 1-interval-connected ring three agents are necessary and sufficient; with pebbles they need \(\Theta(n^{1.5})\) moves.
tight \(3\) vs \(3\) adversarial edge changes
tight \(O(n^{1.5})\) vs \(\Omega(n^{1.5})\) adversarial edge changes
Dynamic graphs with whiteboards
In 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.
tight \(6\) vs \(4\) adversarial edge changes
unknown \(O(m^2)\) vs —

Open questions 6

Eventually emerging black hole, synchronous agents, arbitrary graphs

  1. Do three synchronous agents suffice on arbitrary graphs Kaur et al. 2026a?

Eventually emerging black hole, synchronous agents, oriented ring

  1. 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.

Eventually emerging black hole, asynchronous agents, oriented ring

  1. How many asynchronous agents without pebbles are needed with implicit termination: between 3 and \(n\)? With two pebbles four suffice Bonnet et al. 2026b.

Dynamic graphs with whiteboards

  1. With at most one missing edge per round, do four or five co-located agents suffice? Three do not Kaur et al. 2026b.
  2. 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.
  3. 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.

What the community started looking at

From the start the objective was the minimum number of agents that guarantees success, since every agent that enters the black hole is lost; the number of moves came second Dobrev et al. 2006. Later work replaced whiteboards by tokens Dobrev et al. 2013 Flocchini et al. 2012b Balamohan et al. 2016, turned to synchronous agents where time can be optimised Czyzowicz et al. 2006 Klasing et al. 2007, to dynamic graphs Di Luna et al. 2025b Kaur et al. 2026b, and to Byzantine companions Di Luna et al. 2025a. Recent variants let the black hole appear only during the execution, on rings Bonnet et al. 2026b and on arbitrary graphs Kaur et al. 2026a, or destroy agents only in rounds chosen by the adversary Bhattacharya et al. 2025.

Variant of Collaborative exploration

Locating the black hole means exploring every other node safely, so black hole search is exploration of a dangerous graph by a team, where agents can be lost.

Related problems

Network decontamination: Both are security problems for agents in a hostile network: in black hole search the network destroys agents, in decontamination agents must clear a network that an arbitrarily fast intruder (or contamination) can re-enter.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • When agents fail A node that destroys visitors, a robot that stops, an agent that lies, a searcher that misses the target: the papers motivate each fault by the hardware or the network, and each kind of fault changes a different measure, from team size to feasibility to an exact constant.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Kaur & Saxena 2026 When agents are powerful: Black hole search with verification in time-varying graphs. Black hole search with verification in synchronous dynamic graphs: if there is no black hole, all agents must terminate. With at most one edge missing per round, 3 co-located agents and \(\deg(v_{BH})+1\) scattered agents cannot solve it even with 1-hop visibility and global communication (Theorems 2.1, 2.2); 4 co-located agents with 1-hop visibility and face-to-face communication solve it in \(O(n^4)\) rounds (Theorem 3.2), and \(\deg(v_{BH})+2\) agents from any start with global communication in \(O(\deg(v_{BH})\,m^2)\) rounds (Theorem 4.2). In always-connected dynamic graphs \(n-2\) agents cannot solve it even with full visibility, and \(n-1\) agents with global communication and 1-hop visibility solve it in \(O(n)\) rounds (Theorems 2.3, 5.1). Agents have distinct identifiers and \(O(\log n)\) bits. Read (arXiv v2).
  • Feletti et al. 2026d Safe Exploration of Arbitrary Dynamic Dangerous Networks. Safe exploration of temporally connected dynamic graphs that contain any number of black holes, unknown to the agents: semi-synchronous agents start on arbitrary safe nodes, nodes have whiteboards, and every safe node must be visited (perpetually, or at least once with termination) while at least one agent survives. Without knowledge of the graph, every algorithm loses one agent per port that leads to a black hole, and no algorithm can mark exactly the ports that lead to black holes, even with synchronous agents of unbounded memory (Theorem 4). With \(2\eta' + \sum_{x \in B}\deg(x) + 1\) agents, where \(B\) is the set of black holes and \(\eta'\) the number of transient edges between safe nodes, oblivious anonymous agents explore perpetually with whiteboards of \(O(\Delta)\) bits (Theorem 11), and agents with identifiers and \(O(n\log n)\) bits of memory that know the number of safe nodes explore and terminate (Theorem 16). The algorithms combine a rotor-router with cautious walk. Preprint; read.
  • Bhattacharya et al. 2025 Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole. Perpetual exploration with a Byzantine black hole: in each round the adversary decides whether the black hole destroys the agents on it and those entering it, so it may never be detected. Co-located synchronous agents with distinct identifiers and face-to-face communication, without knowledge of \(n\), must visit infinitely often every node of one component of the graph without the black hole, or of the component of the home base. On paths and trees, 4 agents (any component) and 6 agents (component of the home base) are necessary and sufficient (Theorems 4 to 7 and 36, Corollary 37; the lower bounds hold even when \(n\) is known). In arbitrary graphs, \(2\Delta-1\) agents are necessary when \(\Delta \ge 4\) (Theorem 10) and \(3\Delta+3\) agents with \(O(n\Delta\log n)\) bits each suffice for the component of the home base (Theorem 12). If the black hole destroys agents in every round, perpetual exploration needs \(\Delta+1\) agents (Theorem 66) and \(\Delta+2\) suffice (Remark 67). Read (arXiv v1).
  • Bhattacharya et al. 2024b Black Hole Search in Dynamic Tori. Dynamic oriented \(n \times m\) tori (\(3 \le n \le m\)) in which every row ring and column ring is 1-interval connected; synchronous agents with identifiers that know \(n\) and \(m\), a whiteboard of \(O(1)\) bits at each port. Co-located: \(n+1\) agents cannot locate the black hole (Theorem 1), \(n+c\) agents with \(c \ge 2\) need \(\Omega(m\log n)\) rounds (Theorem 3), \(n+3\) agents take \(O(nm^{1.5})\) rounds and \(n+4\) agents \(O(nm)\) (Theorems 7, 8). Scattered: \(n+2\) agents cannot (Theorem 4), \(n+c\) agents with \(c \ge 3\) need \(\Omega(nm)\) rounds (Theorem 5), \(n+6\) agents take \(O(nm^{1.5})\) rounds and \(n+7\) agents \(O(nm)\) (Theorems 9, 10). Read (arXiv v1).
  • Bhattacharya et al. 2024a Black Hole Search in Dynamic Cactus Graph. Dynamic cactus graphs (every edge on at most one cycle) that stay connected, with whiteboards and co-located synchronous agents with identifiers. With at most one edge missing per round, 2 agents cannot locate the black hole, 3 agents need \(\Omega(n^{1.5})\) moves and rounds and use \(O(n^2)\), and 4 agents need \(\Omega(n)\). With at most \(c\) edges missing (their \(k\)), \(c+1\) agents cannot, and \(2c+3\) agents use \(O(cn)\) rounds and \(O(c^2n)\) moves (Theorems 9 to 11). Read (arXiv v1).
  • Goswami et al. 2024b Perpetual Exploration of a Ring in Presence of Byzantine Black Hole. Perpetual exploration of an oriented ring with a Byzantine black hole (it may let agents pass, destroy them, or erase what is written on it), by synchronous agents with identifiers that know \(n\). Co-located: 3 agents are necessary and sufficient with pebbles or with whiteboards, and 5 suffice face-to-face; scattered: 4 agents with pebbles and 3 with whiteboards are necessary and sufficient (Table 1). Extended to trees and arbitrary graphs in Bhattacharya et al. 2025. Read (arXiv v2).
  • Dobrev et al. 2023 Asynchronous Gathering in a Dangerous Ring. Gathering despite a black hole: \(k\) anonymous asynchronous agents, dispersed in an anonymous ring with whiteboards, must gather and stop at one node, and the question is how many of them can be guaranteed to. Knowing \(k\) but not \(n\): \(k-1\) in an oriented ring; in an unoriented ring \(k-2\) for odd \(k\) and \((k-2)/2\) for even \(k\). Knowing \(n\) but not \(k\): \(k-2\) in an oriented ring, and in an unoriented one \(k-2\) unless \(k\) is even and \(n\) odd, then \((k-2)/2\). One agent more is impossible in each case (Theorems 1, 2 and 10; Table 1), at most \(\lfloor k/2\rfloor\) when neither is known (Theorem 3), and in an unoriented ring \(k-2\) agents can always end within distance 1 of each other. The algorithms take \(O(n)\) time and \(O(nk)\) moves; the one for unknown \(k\) also locates the black hole in \(\Theta(n)\) ideal time, against \(O(n\log n)\) in Dobrev et al. 2007. Read in full.
  • D'Emidio et al. 2015 Explore and repair graphs with black holes using mobile entities. Explore and repair, the model of Cooper, Klasing and Radzik extended by a radius \(r\): \(k\) synchronous labelled agents start at a safe home base of a known graph with \(b\) unknown black holes; an agent that enters a black hole repairs it and is destroyed, with every agent within distance \(r\). Making the graph safe as fast as possible is NP-hard even for \(b = k = 1\) (Theorem 3.1); for \(r > 0\) every strategy needs \(\Omega(n/k + D + r\min\{D, b\} + |K|)\) steps, \(|K|\) the size of a largest clique (Lemma 3.4); for \(r \le 1\) three strategies (snake, scout, parallel scout) take \(O(n)\) steps, which some graphs need, and are compared in experiments. Read (model and theorems).
  • Czyzowicz et al. 2009a Black hole search in directed graphs. Black hole search in a simple strongly connected directed graph with \(n\) nodes and local port labels: agents with polynomial memory start at a home base and share whiteboards. An agent that has crossed an arc cannot walk back to mark it safe, and the number of agents becomes exponential. Let \(\deg_{in}(v_{BH})\) be the in-degree of the black hole \(v_{BH}\) (their \(\Delta\)). For every algorithm and every \(n > \deg_{in}(v_{BH})\), some \(n\)-node digraph needs \(2^{\deg_{in}(v_{BH})}\) agents, even synchronous ones (Theorem 1), whereas \(\deg(v_{BH})+1\) agents always suffice in undirected graphs. In planar digraphs whose planar embedding the agents know, \(2^{\deg_{in}(v_{BH})}+1\) agents suffice (Theorem 2), and in some execution \(2^{\deg_{in}(v_{BH})}-1\) agents enter the black hole (Theorem 3). They ask whether a number of agents that depends on \(\deg_{in}(v_{BH})\) alone suffices in every digraph. Read (model and theorems).
  • Kosowski et al. 2011 Synchronous black hole search in directed graphs. Synchronous agents in the setting of Czyzowicz et al. 2009a: agents with distinct identifiers start at a home base, know \(n\) (or an upper bound on it) and the number \(\deg_{in}(v_{BH})\) of arcs that lead into the black hole (their \(\Delta\)), and every node has a whiteboard accessed in mutual exclusion. \(O(\deg_{in}(v_{BH})\cdot 2^{\deg_{in}(v_{BH})})\) synchronous agents suffice in every strongly connected digraph (Theorem 3.1), against the lower bound \(2^{\deg_{in}(v_{BH})}\) of Czyzowicz et al. 2009a, which answers its question for synchronous agents. With one arc into the black hole, 2 agents are necessary and sufficient, synchronous or not (Theorem 4.1). With two arcs, 4 synchronous agents are necessary and sufficient (Theorem 3.2), while asynchronous agents sometimes need 5 (Theorem 4.2): unlike in undirected graphs, synchrony changes the number of agents. Read (abstract, results and theorem statements).

All settings

The assumption tree (14 settings, 7 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Agents, Cost); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Faults › Black hole appearance › Timing › Knowledge of the graph › Marking nodes › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Knowledge of the graph

0no knowledge of the topology (\(n\) is known)1sense of direction2a map of the graph

Dobrev, Flocchini, Prencipe and Santoro organised black hole search in arbitrary networks around the agents' a priori knowledge: with topological ignorance, \(\Delta+1\) agents are necessary and sufficient and the cost is \(\Theta(n^2)\); with sense of direction two agents suffice, still at cost \(\Theta(n^2)\); with complete topological knowledge two agents suffice at cost \(\Theta(n\log n)\) Dobrev et al. 2006. Knowing \(n\) is the floor of the axis, because they prove that asynchronous black hole search is unsolvable when \(n\) is unknown Dobrev et al. 2006. Sense of direction is the notion of Flocchini, Mans and Santoro: a globally consistent labelling of the ports from which one can decide, from the label sequences alone, whether two walks from a node end at the same node Flocchini et al. 1998 (as defined in Dobrev et al. 2006); Dobrev et al. trace its effect on exploration back to Blum and Kozen's study of the power of a compass Blum & Kozen 1978. The three levels thus separate team size (from \(\Delta+1\) down to \(2\)) and, independently, cost (from \(n^2\) down to \(n\log n\)).

Formal definitions
0topology unknown
Agents know \(n\) but not the topology of \(G\).
1sense 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.
2map
Agents have a map of \(G\) and know their starting position on it.

Marking nodes

0no marking1tokens (pebbles) that agents carry and drop2whiteboards at the nodes

The first black hole search papers gave the agents a whiteboard at every node Dobrev et al. 2007 Dobrev et al. 2006. Flocchini, Ilcinkas and Santoro observe that whiteboards let a protocol assume FIFO links and break symmetry, whereas "the theoretical quest, on the contrary, has been for the weakest interaction mechanism allowing the problem to be solved"; that weaker mechanism is identical tokens, taken from the early work on exploring safe graphs Flocchini et al. 2012b. Dobrev, Flocchini, Královič and Santoro showed that \(\Delta+1\) agents, each with a token that may be placed on a node or a port, locate the black hole without a map at polynomial cost Dobrev et al. 2013 (as summarised in Flocchini et al. 2012b); with a map, Flocchini, Ilcinkas and Santoro gave the first proof that one pebble per agent, on nodes only, matches the whiteboard bounds of two agents and \(\Theta(n\log n)\) moves, even on non-FIFO links Flocchini et al. 2012b. Without a map the equivalence fails for a constant number of tokens: Balamohan, Dobrev, Flocchini and Santoro show that \(\Delta+2\) agents with three tokens are necessary and sufficient, one agent more than with whiteboards Balamohan et al. 2016.

Formal definitions
0no marking
Agents cannot leave information at nodes.
1tokens
Agents carry tokens (pebbles) they can place at nodes or on ports; tokens are identical and carry no other information.
2whiteboards
Every node has a whiteboard that agents read and write under mutual exclusion.

Black hole appearance

0the black hole may appear at any time, at any node (at the home base only after the start)1the black hole is present from the start

Bonnet, Bramas and Lamani let the black hole appear at any time during the execution: "To the best of our knowledge, all previous investigations of the basic Black Hole Search problem assume that the black hole is present in the initial configuration" Bonnet et al. 2026b. An emerging black hole defeats the cautious walk alone, because agents that gather on a node to coordinate may all be destroyed when the black hole appears there Bonnet et al. 2026b. Kaur, Saxena, Mandal and Mondal carried the question from rings to arbitrary graphs Kaur et al. 2026a. Every other setting of this problem has the black hole present from the start.

Formal definitions
0eventually 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.
1present from the start
The black hole is present at time 0, and the home base \(s\) is safe throughout.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.