Mobility Matters
Home›Mobile agents on graphs›Exploration›Collaborative exploration›Exploration of dynamic graphs by teams

Exploration of dynamic graphs by teams

An adversary changes the graph over time; how many agents are needed to explore it?

Problem statement and measurescollapse
round 0missinground 1missinground 2missinground 3missinground 4missinground 5missinground 6missinground 7abStart: a and b on one node; a goes clockwise, b the other wayThe adversary removes a's edge: a waits, b movesNow b is blocked and a moves: someone always advancesAfter N - 1 = 7 rounds every node is visited; both stop
Live exploration of a dynamic ring Di Luna et al. 2020: in every round an adversary removes at most one edge of the ring (1-interval connectivity; the missing edge is dashed red). Two agents start on one node, know \(N = n = 8\) and walk in opposite directions, waiting while their next edge is missing; the adversary can block only one of them, so every round visits a new node, and after \(N - 1\) rounds both stop. One agent alone can be blocked forever.

Agents must visit every node of a dynamic graph: a sequence of graphs \(G_t = (V, E_t)\) on one node set, whose edges are removed round by round by an adversary subject to a connectivity constraint (1-interval connectivity: every \(G_t\) is connected; temporal connectivity: every node can reach every other through edges present at non-decreasing times). The primary measure is the number of agents; the secondary is time in rounds.

Measures: Agents, number of agents needed; Time, rounds.

A first look

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

Imagine guards who must check every station on a circular railway, while the operator closes some piece of track at any moment without warning. We model the railway as a graph: stations are nodes, the pieces of track between neighbouring stations are edges, and each guard is an agent. In the basic version the graph is a ring of \(n\) nodes (the nodes form one cycle, each joined by an edge to its two neighbours). Time runs in rounds: in each round every agent may cross one edge or wait. An adversary (an imagined opponent, the operator of the picture) chooses, in every round, which edges are missing (removed for that round), with one rule: the graph must stay connected in every round (1-interval connectivity); in a ring this means that at most one edge is missing per round. A graph that changes like this is a dynamic graph. The agents must together visit every node; in the version recorded here they also know an upper bound \(N \ge n\) and must stop. We count the agents needed and the rounds.

1AlgorithmTwo agents walking in opposite directions 1-interval-connected rings → Di Luna et al. 2020

The simplest case: two agents start on the same node and know \(N \ge n\).

  1. The two agents set off in opposite directions around the ring (the paper shows how two identical agents can agree on this).
  2. In every round each agent tries to cross the next edge in its direction; if the edge is missing, it waits (it is blocked) and tries again in the next round.
  3. After \(N - 1\) rounds both agents stop.
Why it works and what it costs. At most one edge is missing per round, and until the two agents have between them covered the whole ring they are trying to cross two different edges, so at least one of them moves forward, onto a node that nobody has visited. Each round therefore visits at least one new node, and the \(n - 1\) other nodes are all visited within \(n - 1 \le N - 1\) rounds. Di Luna et al. 2020 handle the harder cases (different starting nodes, no common sense of left and right) with one extra rule, turning back after being blocked for long, and both agents stop after \(3N - 6\) rounds.

Why it matters. It shows that a second agent turns an impossible task into an easy one, because the adversary can only block one of them at a time.

2ImpossibilityOne agent can always be blocked 1-interval-connected rings → Di Luna et al. 2020

A single agent stands on a node of the ring and, in some round, decides to cross one of the two edges at its node. The adversary removes exactly that edge in that round. Removing one edge from a ring leaves a path, which is still connected, so this is allowed. The adversary can do this in every round, so the agent never leaves its starting node.

Why it holds. So at least two agents are needed Di Luna et al. 2020. The same paper also shows that the adversary can prevent two agents that start on different nodes from ever meeting, by removing an edge only at the moment the two would otherwise meet: the agents cannot rely on meeting to coordinate.

Why it matters. The number of agents becomes the main measure on dynamic graphs, because a few agents may be unable to explore at all, whatever time they are given.

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
Time
1-interval-connected rings standard
One agent cannot explore a dynamic ring; two agents with a known bound on \(n\) explore in \(3N-6\) rounds.
tight \(3\) vs \(2\) adversarial edge changes
unknown \(3N-6\) vs —
Temporally connected graphs, arbitrary topology
Perpetual exploration of a temporally connected graph with \(\eta\) transient edges needs exactly \(2\eta+1\) agents.
tight \(2\eta+1\) vs \(2\eta+1\) adversarial edge changes
unknown — vs —

Open questions 1

1-interval-connected rings

  1. With a landmark but no chirality, is \(O(n\log n)\) time necessary? Di Luna et al. 2020

What the community started looking at

In dynamic graphs the community first asked how many agents make exploration possible at all, under each connectivity assumption Di Luna et al. 2020 Gotoh et al. 2021 Saxena & Mondal 2026; time came second.

Variant of Collaborative exploration

When an adversary removes edges, a single agent can be blocked forever; the question shifts from speed to how many agents are needed to visit every node.

All settings

The assumption tree (2 settings, 1 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, Time); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Timing › Topology.

tight near-optimal polynomial gap unknown impossible no variant

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