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

no assumptions›+ static graph, + undirected›+ no faults›+ synchronous, + map

Synchronous agents with a map

verified
Agents: tightCost: polynomial gap

With synchrony, two agents and a map, the question becomes the fastest exploration schedule, which is NP-hard to find.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Faultsno faults+Timingsynchronous rounds+Knowledge of the grapha map of the graph

Not assumed

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.
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: map
Agents have a map of \(G\) and know their starting position on it.
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.

What is known

Agents · number of agents needed (team size)
tight
Two agents.
lower boundnone known
introductory
\(2\)
current best
\(2\)
Cost · total moves (asynchronous) or rounds (synchronous)
polynomial gap
Approximation ratio \(3\frac38\) versus inapproximability \(389/388\).
lower bound
\(\text{NP-hard}\) Klasing et al. 2007
bottleneckcombinatorial hardness
holds when
  • computing an optimal schedule for two agents
  • no \(389/388\)-approximation unless P = NP (APX-hard)
introductory
\(9.3\text{-approx.}\)
current best
\(3\tfrac{3}{8}\text{-approx.}\)

Results, in order of publication

Czyzowicz et al. 2006 introductory
Agents \(2\)Cost \(9.3\text{-approx.}\)
Klasing et al. 2007 current best
Agents \(2\)Cost \(3\tfrac{3}{8}\text{-approx.}\)

Open questions

None recorded for this variant.

Notes

On trees the problem has a \(5/3\)-approximation (CPC 2007, not yet in the bibliography).

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

Byzantine companions, with a map
Agents \(2f+2\)Cost \(O(n+f)\)

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.