PaperlayerView exact revision on arXiv

Source-linked AI summary

Don't Be Afraid to Die: Black Hole Search in Dynamic Graphs with Fewer Agents

Kass Bileski, Avery Miller

arXiv:2609.06850v1cs.DCcs.DS

TL;DR

In scattered-start black-hole search, agents must identify a destructive node while contending with dynamic edges that can make a failed traversal ambiguous. The paper uses cautious exploration and whiteboard clues left by agents that do not return. It proves that 2δBH + 3 agents suffice, with reporting within O(m^2 · δBH) rounds.

  • Problem

    Black-hole search asks whether a team can safely locate the destructive node, with a survivor terminating next to it and outputting the port that leads to it.

    Source: §1.1 · p. 3

  • Method

    The agents run scattered graph exploration with cautious port marking, using evidence left by destroyed agents rather than switching to another strategy.

    Source: §1.3 · p. 5, §2.3 · p. 9

  • Results

    2δBH + 3 agents solve 1-BHS within O(m^2 · δBH) rounds in the stated dynamic-graph setting.

    Source: §1.3 · p. 4, §3 · p. 15

  • Takeaways & Limitations

    After 2δBH agents have been destroyed, the remaining agents can explore safely because every black-hole-adjacent node has a whiteboard clue that solves the task.

    Source: §1.3 · p. 5

    Detailed proofs are omitted for space constraints and are to appear in the journal version.

    Source: §1.3 · p. 5

Abstract

from arXiv · show

We consider a team of synchronous mobile agents operating in a port-labeled network. There is one node in the network, called a black hole, that permanently destroys any agent that visits the node. The team of agents must safely locate the black hole, i.e., at least one agent must survive, terminate its algorithm at a node adjacent to the black hole, and output the port number that leads to the black hole from its current position. In the setting where the network is a 1-bounded 1-interval connected dynamic graph, Kaur et al. (SSS 2025) showed that a team consisting of $2\delta_{BH}+17$ agents is sufficient to solve the task from a scattered configuration, where $\delta_{BH}$ denotes the degree of the black hole node. We show that $2\delta_{BH}+3$ agents are sufficient, nearly matching the $2\delta_{BH}+1$ lower bound provided in Kaur et al. (ICDCN 2025).

1 Preliminaries

The paper studies black-hole search by mobile agents in a dynamic graph with at most one inactive edge per round, starting from an arbitrary scattered configuration. It improves the agent bound for this setting by combining exploration with evidence left by agents destroyed at the black hole.

1.1 The Model and the Problem

  • The model has a fixed underlying graph whose active snapshots remain connected after at most one edge is removed per round, with anonymous nodes and port-labeled incident edges.Agents have unique identifiers, O(log n) bits of internal memory, and access to O(log n)-bit node whiteboards; their initial safe-node placement is arbitrary.Source: §1.1 · p. 2
  • Black-hole search requires a surviving agent to terminate adjacent to the black hole and output the local port leading to it.The algorithm is intended to solve this task for any graph, black-hole location, and starting configuration, and to bound the reporting time.Source: §1.1 · p. 3

1.2 Related Work

  • Earlier scattered-start work used 2δBH + 17 agents by switching to a rooted-search strategy when enough agents were blocked, while a 2δBH + 1 lower bound was known.That approach combined a bound on agents destroyed with a rooted algorithm for agents stuck at an inactive edge.Source: §1.2 · p. 4, §1.3 · p. 5

1.3 Our Results and Approach

  • On any 1-bounded 1-interval connected time-varying graph with n nodes, m edges, and one black hole of underlying-graph degree δBH, 2δBH + 3 agents solve 1-BHS, with at least one reporting within O(m^2 · δBH) rounds.Source: §1.3 · p. 4
  • The new approach never switches strategies: destroyed agents leave repeated port marks that identify the black hole, and after 2δBH deaths the remaining agents can explore safely.A scattered exploration algorithm for at least three agents skips blocked ports so that at least one agent makes progress each round.Source: §1.3 · p. 5
  • The paper states that detailed proofs are omitted because of space constraints and will appear in the journal version.Source: §1.3 · p. 5

2 Algorithm Description

The algorithm combines multi-agent depth-first exploration with whiteboard records and cautious edge traversals. Dispersal and ignore lists manage agents that contend for ports or follow earlier traversals, while paired rounds handle inactive edges and black-hole evidence.

2 Algorithm Description

  • The algorithm combines DFS, cautious traversal, and whiteboard records with dispersal and ignore rules to explore despite inactive edges and identify the black hole.Only the two lowest-ID agents at a node act in a step, limiting simultaneous risk while allowing movement if one is blocked.Source: §2 · p. 5, §2.1 · pp. 7–8, §2.4 · pp. 9–10

2.1 Depth-First Search (DFS)

  • DFS records each agent’s parent port and most recent outgoing port on whiteboards, allowing it to explore unvisited ports and backtrack when exploration is complete.When an agent sees smaller-ID DFS information, it can abandon its traversal and follow that agent’s DFS; DFS numbers distinguish separate runs.Source: §2.1 · pp. 6–8

2.2 Even and Odd Rounds

  • Movement uses paired even and odd rounds: agents attempt moves in even rounds, then learn success or failure and update memory and whiteboards in odd rounds.This lets subsequent decisions account for an inactive edge that blocked the preceding move.Source: §2.2 · p. 8

2.3 Individual Cautious Movement (ICM)

  • Each DFS edge step becomes a three-stage cautious movement: mark the outgoing port, cross and return to clear the mark, then cross again to the known-safe node.A destroyed agent leaves its mark behind, while unsuccessful moves caused by inactive edges are retried; six marked variables suffice at each node.Source: §2.3 · pp. 8–9

2.4 Disperse and Ignore

  • When two agents choose the same port, the lower-ID agent attempts it while the other skips it and ignores the first agent’s DFS information to avoid cycling.Dispersal limits agents stuck at inactive ports to at most two, so three agents performing DFS suffice to guarantee progress each round.Source: §2.4 · pp. 9–10

2.5 Summary of the Algorithm

  • In the summary algorithm, agents retry failed moves, follow eligible smaller-ID DFS records, and use duplicate marked-port records to report the black hole.After successful moves, agents advance ICM stages and clear whiteboard information when required.Source: §2.5 · pp. 10–13

3 Algorithm Analysis

The analysis proves that 1-BHS takes at most 2δ_BH + 3 agents and O(m^2δ_BH) rounds. Its bounds follow from safe tracking of marked ports and progress guarantees for DFS despite inactive edges.

  • At least two of six marked-port variables remain empty at each even-round start, while at most two agents write to them per even round.Source: §3 · pp. 13–14
  • At most 2δ_BH agents visit the black hole because each dangerous port is permanently recorded and can be recorded at most twice.Source: §3 · p. 14
  • Matching marked-port entries identify the black hole: a non-black-hole port can appear in at most one marked variable at an even-round start.Source: §3 · p. 14
  • A DFS uses at most 12m movements with ICM, and the analysis bounds the reporting time by controlling delays from inactive edges.The progress argument uses the three lowest-ID agents and dispersal to prevent them from being stalled at the same port.Source: §3 · p. 15
  • 2δ_BH + 3 agents suffice to solve 1-BHS in O(m^2δ_BH) rounds.Source: §3 · p. 15

A Summary of Variables

The variables track each agent’s DFS and movement state, as well as information that agents leave on node whiteboards. Together, these records include DFS history, marked ports, and agent-specific ignore and cleanup state.

B Pseudocode for Aexplore

The pseudocode coordinates movement, DFS choices, and whiteboard updates. It also reports the black hole when marked-port records match.

Loading 2609.06850v1…