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 measuresexpand

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.

no assumptions›+ connected every round, + undirected, + synchronous

Connected at every step, any graph

verified
Agents: polynomial gapTime: unknown

Against an adaptive adversary that keeps every snapshot connected, \(2m-n+1\) silent agents explore any graph, and \(m-n+1\) are needed even with a central offline scheduler.

Assumed (added on the last edge are outlined)

+Graph dynamicsdynamic graph, connected in every round (1-interval connected)+Edge directionundirected+Timingsynchronous rounds

Not assumed

Topologyarbitrary connected graph
Formal definitions of this setting
Graph dynamics: connected every round
\(\mathcal G=(G_t)_{t\ge0}\) is 1-interval connected if every snapshot \(G_t=(V,E_t)\) is connected. More generally it is \(T\)-interval connected if for every \(t\) the graph \(\bigl(V,\bigcap_{i=t}^{t+T-1}E_i\bigr)\) is connected.
Edge direction: undirected
\(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
Timing: synchronous
Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
Topology: any topology
\(G\) is any connected graph in the class allowed by the other axes.

What is known

Agents · number of agents needed
polynomial gap
\(m-n+1\) against \(2m-n+1\); the ratio is unbounded on graphs with few cycles.
lower bound
\(m-n+1\) Dobrev et al. 2020a
bottleneckadversarial edge changes
holds when
  • all agents start at one node (Theorem 2)
  • the adversary blocks one agent on each non-tree edge of a DFS tree
  • holds even for a central offline scheduler that sees all agents but not the future snapshots
introductory—
current best
\(2m-n+1\)
sense of direction: from the labels of traversed edges an agent can name nodessilent agents: a mutual-exclusion mechanism lets one agent per port move, and the others learn that they failedany starting nodes
Time · rounds
unknown
No lower bound; \(O(n^9)\) only with \(O(n^4)\) agents.
lower boundnone known
introductory—
current best
\(O(n^9)\)
agents also see how many agents are at their node, and their actions

Results, in order of publication

Dobrev et al. 2020a current best
Agents \(2m-n+1\)
sense of direction: from the labels of traversed edges an agent can name nodessilent agents: a mutual-exclusion mechanism lets one agent per port move, and the others learn that they failedany starting nodes

Introductory and current best (Theorem 1); whether this algorithm explores in polynomial time is not known.

Dobrev et al. 2020a also
Agents \(O(n^4)\)Time \(O(n^9)\)
agents also see how many agents are at their node, and their actions

Theorem 3: polynomial time with more agents.

Open questions

  1. Does the algorithm with \(2m-n+1\) agents explore in polynomial time? Posed in Dobrev et al. 2020a.

Notes

Every snapshot is a connected spanning subgraph of an underlying graph with \(n\) nodes and \(m\) edges, chosen by an adversary that sees the agents' moves. Checked against the full text of Dobrev et al. 2020a.

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

Temporally connected graphs, arbitrary topology
Agents \(2\eta+1\)

Lower bounds from stronger settings hold here

1-interval-connected rings
Agents \(2\)

Branches from here

1-interval-connected rings

+ring
One agent cannot explore a dynamic ring; two agents with a known bound on \(n\) explore in \(3N-6\) rounds.

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