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

Unknown graphs, monotone strategies

verified

Agents: tightMoves: unknown

Clearing an unknown graph monotonically costs a factor \(\Theta(n/\log n)\) in agents over the optimum.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected

Not assumed

TimingasynchronousKnowledgethe topology is unknownTopologyarbitrary connected graph

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: unknown graph: Agents know nothing about \(G\).
Topology: any topology: \(G\) is any connected graph in the class allowed by the other axes.

What is known

Agents · number of agents needed

tight

Competitive ratio \(\Theta(n/\log n)\).

lower bound

\(\Omega(n/\log n)\cdot\text{opt}\) Ilcinkas et al. 2009

bottleneckunknown topology

holds when

monotone connected strategies
holds even for synchronous agents

introductory—

current best

\(O(n/\log n)\cdot\text{opt}\)

Ilcinkas et al. 2009

Moves · total moves (or time, as stated)

unknown

—

lower boundnone known

introductory—

current best—

Results, in order of publication

Ilcinkas et al. 2009 current best

Agents \(O(n/\log n)\cdot\text{opt}\)

Achievable even asynchronously.

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

No catalogued weaker setting.

Lower bounds from stronger settings hold here

Trees

Hypercubes

Agents \(\Omega(n/\sqrt{\log n})\)

Branches from here

Topology

+known graph

splits into 2 branches

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