Mobility Matters
Home›Mobile agents on graphs›Exploration›Broadcast by agents in dynamic graphs

Broadcast by agents in dynamic graphs

One agent holds a message; an adversary changes the graph every round, keeping it connected. How many agents are needed so that the message always reaches every agent?

Problem statement and measurescollapse
1223344Start: n − 1 = 4 agents, one empty node; agent 1 is the source agentRound 1: a path of two edges joins 1 and 2; they meetRound 2: two nodes are empty; agent 2 steps into oneRound 3: again a path of two edges; 1 and 3 meetRound 4: agents shift along an open path to fill an empty nodeFinal (round 5): 1 and 4 meet; every agent holds the message
Broadcast with \(n - 1\) agents Das et al. 2026b on the complete graph \(K_5\), where \(n - 1\) agents are also necessary. Agent 1 is the source agent (green), agents 2 to 4 are ignorant (grey), and one node is empty. In every round the adversary opens a snapshot (thick edges), here a path through all nodes chosen to keep the source agents away from the ignorant ones. With one empty node, some source agent and some ignorant agent are still at most two edges apart, and they meet. A meeting leaves two nodes empty, so in the next round the agents shift one edge along an open path to fill one of them. One frame per round.

\(k \ge 2\) agents with distinct identifiers stand on distinct nodes, chosen by an adversary, of a connected undirected graph \(G = (V, E)\) with \(n\) nodes. One agent, the source agent, holds a message; the other \(k - 1\) are ignorant agents. Time runs in synchronous rounds. At the start of every round the adversary chooses the snapshot \(G_t\), any connected spanning subgraph of \(G\) (the dynamic graph is 1-interval connected); every agent then sees \(G_t\) and the position and status of every agent (global visibility), and moves along one edge of \(G_t\) or stays. An ignorant agent that is on the same node as a source agent receives the message and becomes a source agent; no message travels in any other way. Broadcast is solved when every agent holds the message. The question is, for each graph \(G\), the least \(k\) with which the agents solve broadcast against every adversary and every initial placement; time is the number of rounds.

Measures: Agents, the least number \(k\) of agents, the source agent included, with which broadcast is solved against every adversary, in the worst case over the graphs of the setting with \(n\) nodes; Time, rounds until every agent holds the message.

A first look

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

Picture a building whose rooms are joined by corridors, and a saboteur who, each minute, may lock any corridors, as long as every room can still be reached from every other. The building is a graph: rooms are its nodes and corridors its edges. A few agents (small mobile machines) stand in different rooms. One of them, the source agent, carries a message; the others are ignorant agents. Time runs in rounds. At the start of each round the saboteur, called the adversary, chooses which edges are open; the open edges form the snapshot of that round, and the snapshot must connect all nodes. Every agent sees the whole snapshot and where every agent is and whether it holds the message (global visibility). Then each agent crosses one open edge or stays. An ignorant agent learns the message only by standing on the same node as an agent that holds it, and then holds it too. Broadcast is solved when every agent holds the message. The adversary also chooses where the agents start. The question is how many agents \(k\) (the source agent included) are needed on a given graph for the agents to always win.

1AlgorithmFill all but one node Dynamic graph, any topology → Das et al. 2026b

Suppose there are \(k = n - 1\) agents on a graph with \(n\) nodes, so at most one node is empty.

  1. In every snapshot there is a path from a source agent to an ignorant agent, because the snapshot connects all nodes.
  2. Take a shortest such path. Its inner nodes hold no agent that could shorten it, so at most one inner node, the empty one, lies on it: the source agent and the ignorant agent are at most two edges apart.
  3. Both step towards each other along that path (or one steps onto the other's node) and they meet in this round. Now there is one more source agent.
  4. Now two agents share a node, so two nodes may be empty. In the next snapshot, take a path from the shared node to an empty node; every agent on it moves one edge along it, so that again at most one node is empty. Repeat until no ignorant agent is left.
Why it works and what it costs. Every repetition turns at least one more ignorant agent into a source agent, so the agents win. The argument works on every graph, so \(n - 1\) agents always suffice Das et al. 2026b. On the complete graph \(K_n\) this is also necessary: with only \(n - 2\) agents two nodes are empty, and the adversary keeps open a spanning tree in which every ignorant agent is at least three edges from every source agent, so no meeting ever happens. On sparser graphs far fewer agents suffice: three on every ring with at least five nodes, two on every tree.

Why it matters. It gives the upper bound \(n - 1\) that holds on every graph, and its counting (how close the source agent is forced to come to an ignorant agent) is the measure every later bound refines.

2ImpossibilityTwo agents on a ring never meet Dynamic rings → Das et al. 2026b

Take a ring with \(n \ge 5\) nodes, one source agent and one ignorant agent.

  1. In every round the adversary removes one edge of the shorter path between the two agents. The snapshot is still a path through all nodes, so it is connected.
  2. The two agents could meet in this round only if they were at most two edges apart along an open path.
  3. The open path between them is the longer way around the ring, which has at least three edges because \(n \ge 5\).
  4. So they never meet, whatever they do.
Why it holds. With two agents broadcast is impossible on every ring with at least five nodes. A third agent defeats this adversary. The two ignorant agents walk towards the source agent from opposite sides; the adversary can remove only one edge of the ring per round, so one of them gets closer in every round and eventually meets the source agent. The two source agents then walk around the ring in opposite directions and one of them meets the last ignorant agent. So three agents always solve broadcast Das et al. 2026b.

Why it matters. It shows the adversary's only weapon, cutting the short way between a source agent and an ignorant agent, and how extra agents beat it by approaching from several sides.

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
Dynamic graph, any topology standard
On a 1-interval connected graph, \(n - 1\) agents always suffice, and the complete graph needs them all; the least number for a given graph is not characterised.
tight \(n-1\) vs \(n-1\) adversarial edge changes
unknown — vs \(\lceil D/2 \rceil\) distance
Dynamic rings
Three agents are necessary and sufficient on every ring with at least five nodes; two suffice on smaller rings.
tight \(3\) vs \(3\) adversarial edge changes
unknown — vs —
Dynamic complete graphs
On \(K_n\) exactly \(n - 1\) agents are needed: all nodes but one occupied.
tight \(n-1\) vs \(n-1\) adversarial edge changes
unknown — vs —
Dynamic bipartite graphs
On bipartite graphs whose two sides have at least three nodes each, \(n - 3\) agents suffice, and complete bipartite graphs need them.
tight \(n-3\) vs \(n-3\) adversarial edge changes
unknown — vs —
Dynamic hypercubes
On \(Q_j\) with \(j \ge 3\) between \(n/2\) and \(n - 3\) agents are needed; exactly \(5\) on \(Q_3\).
tight \(n-3\) vs \(n/2\) adversarial edge changes
unknown — vs —
Dynamic grids
On a \(\sqrt n \times \sqrt n\) grid between \((\sqrt n - 1)^2 + 1\) and \(n - 3\) agents are needed; on a \(2 \times b\) grid, \(b\) or \(b + 1\).
tight \(n-3\) vs \((\sqrt n-1)^2+1\) adversarial edge changes
unknown — vs —
Static graph
Without edge changes two agents suffice on every graph and broadcast takes \(\Theta(D)\) rounds.
tight \(2\) vs —
tight \(O(D)\) vs \(\lceil D/2 \rceil\) distance

Open questions 5

Dynamic graph, any topology

  1. Which graph property determines the least number of agents that solve broadcast on a graph \(G\)? Edge density, edge connectivity and the number of redundant edges do not Moses Jr. et al. 2025; is there an analogue of dismantlability, which characterises cop-win graphs? Moses Jr. et al. 2026
  2. How many rounds do the agents need when they win, as a function of \(n\) and \(D\)? Only lower bounds of order \(D\) are known Moses Jr. et al. 2026.
  3. Can broadcast be solved with weaker agents than global visibility, for example agents that see only the source agent? Das et al. 2026b

Dynamic hypercubes

  1. How many agents are needed on \(Q_j\) for \(j \ge 4\): \(n/2\), \(n - 3\), or in between? Das et al. 2026b

Dynamic grids

  1. Close the gap between \((\sqrt n - 1)^2 + 1\) and \(n - 3\) agents on the \(\sqrt n \times \sqrt n\) grid Das et al. 2026b.

What the community started looking at

Broadcast by agents was posed for dynamic graphs by Das, Giachoudis, Luccio and Markou, who asked for the least number of agents per topology: two on trees, three on rings, linear in \(n\) on grids, hypercubes and complete graphs, which suggested that the number of redundant edges decides the answer Das et al. 2026b. Moses, Redlich and Stock showed that edge density does not decide it, nor edge connectivity Moses Jr. et al. 2025, and recast the problem as a game between agents and adversary in the spirit of cops and robber, with general constructions for both winners and first bounds on the time Moses Jr. et al. 2026.

Related problems

Exploration of dynamic graphs by teams: The same adversary: in every round it may remove any edges as long as the snapshot stays connected (1-interval connectivity), and the primary measure is the number of agents needed in both problems.

Gathering in graphs: Every ignorant agent must meet a source agent, so any algorithm that gathers all agents on one node in a setting also solves broadcast there; broadcast asks only for the meetings that pass the message on.

All settings

The assumption tree (7 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 › Identifiers › Communication › Timing › Initial configuration › 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.