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 measurescollapse
sssssssss12Start: all nodes contaminated; agents 1, 2 at sAgent 1 guards s; agent 2 cleans the smaller branch bBranch b is clean: the guard at s is no longer neededBoth enter branch a; agent 1 guards a, agent 2 cleans a2Last branch: the guard joins; every node is clean with 2 agents
Decontamination of a tree Barrière et al. 2002 with the rule "guard the node, clean its branches one by one": every node is contaminated (red) and agents start at the home base \(s\); a node is clean (green) once visited and would be recontaminated if left unguarded next to a red node. One agent guards \(s\) while the other cleans the smaller branch and comes back; then the guard is free, both enter the other branch, and the same rule is applied at \(a\). Nothing is ever recontaminated, the clean part stays connected, and two agents suffice.

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).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine a network of pipes filled with a contaminating gas: cleaners must clean every junction, but gas flows back into any clean junction that is left unguarded next to one still full of gas. We model the network as a graph: junctions are nodes, pipes are edges, and each cleaner is an agent. At the start every node is contaminated. An agent makes a node clean by standing on it; a clean node with no agent on it becomes contaminated again as soon as one of its neighbours is contaminated (recontamination). An agent that stays on a clean node to prevent this is a guard. All agents start at one node \(s\), the home base, and move along edges (one move is one traversal of one edge), and the clean part must always be connected. In the basic version the graph is a tree (a graph without cycles) whose map the agents know. The task: clean every node; we count the agents needed first, and moves and time second.

1AlgorithmGuard the node, clean its branches one by one Trees →

A standard approach on a tree, rooted at the home base \(s\). Write \(a(v)\) for the number of agents this method uses to clean the branch of node \(v\): \(v\) together with all nodes below it.

  1. A node with no children (a leaf) needs one agent: \(a(v) = 1\).
  2. At a node \(v\), sort the branches of its children so that the first one needs the most agents.
  3. Keep one agent on \(v\) as a guard. Clean the other branches one after another, each with its own team; when a branch is clean, its team comes back to \(v\) to clean the next one.
  4. Finally the guard is no longer needed at \(v\) (all its other neighbours are clean), so it joins the team for the first, largest branch.
  5. This gives \(a(v) = \max\big(a(c_1),\ a(c_2) + 1\big)\), where \(c_1\) and \(c_2\) are the children with the largest and second-largest needs.
Why it works and what it costs. No clean node is ever left unguarded next to a contaminated one, so nothing gets recontaminated, and the clean part always contains \(s\) and stays connected. A path needs one agent; a star centred at \(s\) needs two; a complete binary tree of height \(h\) needs \(h + 1\) with this rule, so about \(\log n\) agents for \(n\) nodes. Barrière et al. 2002 compute the smallest possible team for any tree, and a strategy for it, in linear time; this primer does not claim that the simple rule above always matches it.

Why it matters. The idea of a guard that waits at a node until its last branch is clean underlies decontamination strategies on trees and on many structured networks.

2Lower boundOne agent cannot clean a cycle Unknown graphs, monotone strategies →

A standard argument. Let the graph be a ring and let one agent start at \(s\). As soon as the agent steps to a neighbour, \(s\) is unguarded, and its other neighbour is still contaminated, so \(s\) becomes contaminated again. The agent can never have more than its current node clean.

Why it holds. So any graph containing a cycle needs at least two agents: one guards while the other advances. More generally, the team must be large enough to guard every clean node that touches a contaminated node at every moment, which is why the answer depends on the shape of the graph (for the hypercube, \(\Theta(n/\sqrt{\log n})\) agents for \(n\) nodes Flocchini et al. 2008c).

Why it matters. It shows the basic counting idea of the problem: count the boundary between clean and contaminated parts that must be guarded.

3Lower boundThe adversary grows the tree as you clean it Unknown graphs, monotone strategies → Ilcinkas et al. 2009

Now the agents do not know the graph, and they must never let a clean part become contaminated again (the strategy is monotone). An adversary (an imagined opponent) builds the graph while the agents clean it Ilcinkas et al. 2009. Whenever an agent crosses an edge into the unknown, the adversary attaches at the far end a new node with two more unexplored edges. Every clean node that still has an unexplored edge must be guarded, because the edge may lead to contamination. When the graph has reached \(n\) nodes, the adversary stops adding edges: the result is a tree in which each node has at most three edges.

Why it holds. At the end, every parent of a leaf in this tree has had to be guarded, and there are at least about \(n/4\) such nodes, so the protocol used at least about \(n/4\) agents. A team that knew the tree in advance could clean it with only \(O(\log n)\) agents. So not knowing the graph costs a factor \(\Omega(n/\log n)\) in team size, and Ilcinkas et al. 2009 give an algorithm that achieves this factor, even for asynchronous agents.

Why it matters. It is a clean example of a competitive lower bound: comparing a distributed team without a map to the best team with a map.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Agents
Moves
Unknown graphs, monotone strategies
Clearing an unknown graph monotonically costs a factor \(\Theta(n/\log n)\) in agents over the optimum.
tight \(O(n/\log n)\cdot\text{opt}\) vs \(\Omega(n/\log n)\cdot\text{opt}\) unknown topology
unknown — vs —
Trees standard
On trees the minimum team and a strategy are computed in linear time.
tight \(\text{optimal}\) vs —
unknown — vs —
Hypercubes
A hypercube needs \(\Theta(n/\sqrt{\log n})\) agents, matching its pathwidth.
tight \(O(n/\sqrt{\log n})\) vs \(\Omega(n/\sqrt{\log n})\) pathwidth
unknown \(O(n\log n)\) vs —
Dynamic graphs, monotone strategies
In a 1-interval connected dynamic graph whose edges may stay missing indefinitely, \(D+2(m-n+1)\) co-located synchronous agents clean an unknown graph monotonically, \(m-n+1\) being its cyclomatic number; on wheels \(n\) agents are needed.
polynomial gap \(D+2(m-n+1)\) vs \(n-1\) guarding the boundary
unknown \(O(n^2)\) vs —

Open questions 1

Dynamic graphs, monotone strategies

  1. How many co-located agents are necessary and sufficient to clean every 1-interval connected dynamic graph monotonically, as a function of \(n\), \(m\) and \(D\)? \(D+2(m-n+1)\) suffice, and \(n-1\) (on \(K_{n/2,n/2}\)) and \(n\) (on wheels) can be necessary Bar et al. 2026.

What the community started looking at

From the start the objective was the minimum number of agents Barrière et al. 2002, first on special topologies Flocchini et al. 2008c and then on unknown graphs, where the question becomes the competitive ratio against the optimal team Ilcinkas et al. 2009. Monotone strategies in dynamic graphs, whose edges may disappear, were studied by Bar et al. 2026.

Related problems

Black hole search: Both are security problems for agents in a hostile network: in black hole search the network destroys agents, in decontamination agents must clear a network that an arbitrarily fast intruder (or contamination) can re-enter.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Saini et al. 2026 Cops and Lethal Robber on Rings: A Distributed Perspective. Cops and a lethal robber on a ring: synchronous agents (cops) with distinct identifiers and \(O(\log n)\) bits, placed at arbitrary nodes and knowing nothing about the ring, face an invisible robber that knows their algorithm, moves arbitrarily fast along paths without agents between the agents' moves, may not enter a node with an agent, and destroys every agent that enters its node; the agents win when they occupy both neighbours of the robber. \(n\) agents never suffice, even when they start at one node (Theorem 2.1), and \(\max\{\sigma+\lfloor\log\sigma\rfloor+4,\ n-\sigma+4\}\) agents win within \(O(n^3)\) rounds, where \(\sigma\) is the length of the part of the ring between the nearest agents that initially contains the robber (Theorem 4.1; their \(\rho\) is \(\sigma\) here); from a single starting node this is \(n+\lfloor\log n\rfloor+4\) (Remark 4.1). The robber is an arbitrarily fast intruder that also destroys agents, so the problem combines intruder capture with black hole search. Preprint; read.
  • Giachoudis et al. 2026 Black Virus Decontamination of synchronous ring networks by initially scattered mobile agents. Black virus decontamination of synchronous rings by initially scattered agents: a contaminated node that, when visited, destroys the agent and infects its unguarded neighbours. Abstract of the SIROCCO 2020 version read.
  • Daadaa et al. 2016 Network Decontamination with a Single Agent. Decontamination with temporal immunity: the immunity number, the least time a clean node can stay exposed to a contaminated neighbour, for one agent on several graph classes. Abstract read.
  • Flocchini et al. 2016b Network decontamination under \(m\)-immunity. Decontamination with immunity: a clean node left without an agent is recontaminated only when at least a threshold number of its neighbours are contaminated (the usual model has threshold 1). For \(d\)-dimensional meshes, tori and trees, monotone algorithms whose team shrinks as the threshold grows (on a mesh one agent once the threshold reaches \(d\), Theorem 1), lower bounds on the team that match for some thresholds (Theorems 2, 4, 5), and \(\Theta(n)\) moves, which is optimal. The agents are synchronous; with one more agent the algorithms work asynchronously. Read (model and theorems).
  • Luccio & Pagli 2016 More agents may decrease global work: A case in butterfly decontamination. Decontamination of butterfly networks with an immunity threshold, judged by work: the number of agents times the number of parallel steps, at least \(n\). For some thresholds a protocol with a larger team needs less work than the protocol with the smallest team known; optimality is shown only in simple cases, and lower bounds on agents and steps are left open. Read (model, protocols and costs).
  • Kameda et al. 2016 An alternative proof for the equivalence of ∞-searcher and 2-searcher. A continuous relative: one agent inside a simple polygon must detect an intruder that moves arbitrarily fast. An agent with two flashlights can search every polygon that an agent with a light in all directions can, as conjectured in 1992 and proved by Park et al. in 2001; a simpler proof through a 2-link visibility diagram of the polygon (Theorems 1–3). Read (statements and outline).

All settings

The assumption tree (4 settings, 2 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Agents, Moves); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Timing › Knowledge › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Knowledge

0the topology is unknown1the topology is known

Barrière, Flocchini, Fraigniaud and Santoro introduced contiguous search by mobile agents, in which agents cannot jump and the cleared part must stay connected; they solved it on trees with a linear-time algorithm that computes the minimum team and its strategy, and stressed that the algorithm is naturally distributed, so a tree network can compute its own strategy Barrière et al. 2002 (abstract read). Later work on specific topologies also builds the strategy from the known structure; for hypercubes, Flocchini, Huang and Luccio use a coordinator that leads the other agents Flocchini et al. 2008c. The unknown level asks what is lost when searchers must clear a graph they discover as they go. Blin, Fraigniaud, Nisse and Vial cleared any unknown asynchronous anonymous graph with whiteboards using at most one searcher more than the monotone connected search number from the homebase, each searcher with \(O(\log k)\) bits of memory (Theorem 1); the clearing is connected but not necessarily monotone, and the number of moves may be exponential Blin et al. 2008; Ilcinkas, Nisse and Soguet showed that if clearing must also be monotone, a protocol with no a priori information about the graph has competitive ratio \(\Theta(n/\log n)\) in the number of searchers, the lower bound holding even for synchronous searchers on trees of maximum degree 3 Ilcinkas et al. 2009.

Formal definitions
0unknown graph
Agents know nothing about \(G\).
1known graph
The topology is known to the agents (or to a coordinator).

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