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, + ring

1-interval-connected rings

standard settingverified
Agents: tightTime: unknown

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

Assumed (added on the last edge are outlined)

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

Not assumed

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: ring
\(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.

What is known

Agents · number of agents needed
tight
Two (with a bound on \(n\)).
lower bound
\(2\) Di Luna et al. 2020
bottleneckadversarial edge changes
holds when
  • one agent cannot explore
  • anonymous agents without a landmark and with \(n\) unknown cannot explore with termination at all
introductory
\(2\)
a known bound \(N \ge n\)
current best
\(3\)
identifiers, no landmark, no edge-crossing detection
Time · rounds
unknown
\(O(n\log n)\) with a landmark but no chirality; whether that is necessary is open.
lower boundnone known
introductory
\(3N-6\)
a known bound \(N \ge n\)
current best
\(3N-6\)
a known bound \(N \ge n\)

Results, in order of publication

Di Luna et al. 2020 introductory
Agents \(2\)Time \(3N-6\)
a known bound \(N \ge n\)
Mandal et al. 2023 also
Agents \(3\)
identifiers, no landmark

Explicit termination with three agents.

Das et al. 2022 also
Agents \(3\)
identifiers, no landmark, no edge-crossing detection

Open questions

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

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

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.