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

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.

A node with no children (a leaf) needs one agent: \(a(v) = 1\).
At a node \(v\), sort the branches of its children so that the first one needs the most agents.
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.
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.
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. 2008).

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 —

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. 2008 and then on unknown graphs, where the question becomes the competitive ratio against the optimal team Ilcinkas et al. 2009.

All settings

The assumption tree (3 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

No assumptions · 1 branches by graph dynamics Nothing is assumed on any axis.
- +static graph+undirected
  Unknown graphs, monotone strategies Clearing an unknown graph monotonically costs a factor \(\Theta(n/\log n)\) in agents over the optimum.
  - +known graph
    Topology · 2 branches
    - +tree
      Trees standard setting On trees the minimum team and a strategy are computed in linear time.
    - +hypercube
      Hypercubes A hypercube needs \(\Theta(n/\sqrt{\log n})\) agents, matching its pathwidth.

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. 2008 (abstract read). 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 graph with one searcher more than the optimum, but not monotonically and possibly in exponentially many steps Blin et al. 2008 (as reported by Ilcinkas et al. 2009); 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.