Mobility Matters
Home›Mobile agents on graphs›Exploration›Network decontamination

Network decontamination

A team of agents must clean a contaminated network, or equivalently capture an invisible, arbitrarily fast intruder, using as few agents as possible.

Problem statement and measuresexpand

All nodes are initially contaminated. A node is cleaned when an agent visits it and is recontaminated when it has a contaminated neighbour and no agent guards it (stands on it). Agents move along edges from a home base \(s\), the node where they all start; the clean part must stay connected. Agents is the number needed (the primary measure); moves (edge traversals) and time are secondary.

Measures: Agents, number of agents needed; Moves, total moves (or time, as stated).

no assumptions›+ static graph, + undirected›+ known graph›+ hypercube

Hypercubes

verified
Agents: tightMoves: unknown

A hypercube needs \(\Theta(n/\sqrt{\log n})\) agents, matching its pathwidth.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Knowledgethe topology is known+Topologyhypercube

Not assumed

Timingasynchronous
Formal definitions of this setting
Graph dynamics: static graph
\(G_t=G\) for all \(t\): the edge set never changes.
Edge direction: undirected
\(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
Timing: asynchronous
Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
Knowledge: known graph
The topology is known to the agents (or to a coordinator).
Topology: hypercube
\(G=Q_j\): nodes are the \(n=2^j\) binary strings of length \(j\), adjacent when they differ in one bit.

What is known

Agents · number of agents needed
tight
\(\Theta(n/\sqrt{\log n})\).
lower bound
\(\Omega(n/\sqrt{\log n})\) Flocchini et al. 2008
bottleneckpathwidth
holds when
  • connected monotone strategies
introductory—
current best
\(O(n/\sqrt{\log n})\)
Moves · total moves (or time, as stated)
unknown
—
lower boundnone known
introductory—
current best
\(O(n\log n)\)

Results, in order of publication

Flocchini et al. 2008 current best
Agents \(O(n/\sqrt{\log n})\)Moves \(O(n\log n)\)

Introductory and current best (with a coordinator); with visibility, \(n/2\) agents in \(O(\log n)\) time.

Open questions

None recorded for this variant.

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

Unknown graphs, monotone strategies
Agents \(O(n/\log n)\cdot\text{opt}\)

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.