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).
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Agents
Moves
tight
\(O(n/\log n)\cdot\text{opt}\) vs \(\Omega(n/\log n)\cdot\text{opt}\)
unknown topology
unknown
— vs —
tight
\(O(n/\sqrt{\log n})\) vs \(\Omega(n/\sqrt{\log n})\)
pathwidth
unknown
\(O(n\log n)\) vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.