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

no assumptions›+ static graph, + undirected›+ no faults›eventually emerging, + synchronous

Eventually emerging black hole, synchronous agents, arbitrary graphs

verified

Agents: tightCost: unknown

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.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Faultsno faults+Timingsynchronous rounds

Not assumed

Black hole appearancethe black hole may appear at any time, at any node (at the home base only after the start)Knowledge of the graphno knowledge of the topology (\(n\) is known)Marking nodesno markingTopologyarbitrary connected graph

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: topology unknown: Agents know \(n\) but not the topology of \(G\).
Marking nodes: no marking: Agents cannot leave information at nodes.
Topology: any topology: \(G\) is any connected graph in the class allowed by the other axes.

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 and face-to-face communication, and use neither pebbles nor whiteboards. Time is counted from the appearance of the black hole.

What is known

Agents · number of agents needed (team size)

tight

3 or 4.

lower bound

\(3\) Bonnet et al. 2026b

bottleneckagents lost in the black hole

holds when

ring bound (Theorem 1 of Bonnet et al. 2026b): a ring is a graph, and the bound holds even with whiteboards, knowledge of \(n\) and an oriented ring

introductory—

current best

\(4\)

Kaur et al. 2026a preprint

knows \(n\) (level 0 of this problem); without it, polynomial time if the black hole appears within polynomial time (Remark 3.1)\(O(\log n)\) bits of memory per agent

Cost · total moves (asynchronous) or rounds (synchronous)

unknown

No time lower bound.

lower boundnone known

introductory—

current best

\(\mathrm{poly}(n)\)

Kaur et al. 2026a preprint

knows \(n\) (level 0 of this problem); without it, polynomial time if the black hole appears within polynomial time (Remark 3.1)\(O(\log n)\) bits of memory per agent

Results, in order of publication

Kaur et al. 2026a preprint current best

Agents \(4\)Cost \(\mathrm{poly}(n)\)

knows \(n\) (level 0 of this problem); without it, polynomial time if the black hole appears within polynomial time (Remark 3.1)\(O(\log n)\) bits of memory per agent

Introductory and current best (Theorem 3.1, Remark 3.2): the agents follow a universal exploration sequence and replace each move by a cautious chain movement, after which the two pairs of agents stand on two adjacent nodes; the time is the length of a universal exploration sequence for \(n\) nodes. Any single-agent exploration can be simulated in the same way (Remark 3.3); with depth-first search and \(O(\log\Delta)\) bits of storage per node it takes \(O(m)\) rounds. A preprint.

Open questions

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

Notes

Kaur, Saxena, Mandal and Mondal extend the model of Bonnet et al. 2026b from rings to arbitrary static graphs. Checked against Section 3 of the full text of Kaur et al. 2026a (arXiv v2).

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.