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).
Dynamic graphs, monotone strategies
draftIn 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.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: connected every round
- \(\mathcal G=(G_t)_{t\ge0}\) is 1-interval connected if every snapshot \(G_t=(V,E_t)\) is connected. More generally it is \(T\)-interval connected if for every \(t\) the graph \(\bigl(V,\bigcap_{i=t}^{t+T-1}E_i\bigr)\) is connected.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Knowledge: unknown graph
- Agents know nothing about \(G\).
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
Statement for this variant
The graph is the footprint \(G\) (with \(n\) nodes, \(m\) edges and diameter \(D\)) of a dynamic graph that is connected in every round: the adversary may remove any edges as long as the graph stays connected, and a missing edge may stay missing for ever. \(m-n+1\) is the cyclomatic number of \(G\), the number of edges outside a spanning tree. Nodes and edges start contaminated: an agent cleans a node by visiting it and an edge by crossing it, and a clean node or edge becomes contaminated again when a path without agents joins it to a contaminated node or edge. The strategy must be monotone. Agents start at a home base \(s\) chosen by the adversary, are synchronous, have distinct identifiers, communicate only at the same node, and know nothing about \(G\); at a node they see which incident edges are present and which are contaminated.
What is known
- Theorem 1: \(n-2\) co-located agents fail on \(K_{n/2,n/2}\), \(n > 4\)
- holds even when every missing edge reappears within a bounded time
- Theorem 2 and Corollary 1: \(m-n+1\) co-located agents fail on a wheel with \(n-1\) rim nodes, where \(m-n+1 = n-1\), starting at the hub
- the adversary keeps every rim edge missing until each rim node is guarded, then restores them all
- needs edges that may stay missing indefinitely
Results, in order of publication
Introductory and current best (Theorem 5; time from Lemma 6). Every node becomes clean; an edge that never reappears cannot be cleaned (Remark 5).
Theorem 4 and Corollary 2.
Theorem 3: agents settle on the nodes in breadth-first order and one agent then cleans the remaining edges; fewer agents than \(D+m-n+1\) on dense graphs.
Open questions
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.
Notes
Checked against the full text of Bar et al. 2026 (arXiv v1; the cited CALDAM 2026 version was not read). Bar, Barik, Bhattacharya and Mandal call this model of dynamics indefinite edge disappearance; in their finite time edge reappearance model every missing edge reappears within \(\delta\) rounds (their \(T\) is \(\delta\) here, their \(k\) is \(m-n+1\) and their \(d\) is \(D\)). It is a special case, so its lower bounds hold here. The algorithm of Theorem 5 keeps one agent at each node with a missing incident edge until the edge reappears, and one more agent at a node with two or more visible contaminated edges, while the rest of the team continues a depth-first search. Lemma 1 states that on some graph of diameter \(D\) fewer than \(D\) co-located agents fail, in both models; it is not recorded as a bound here, because its proof (on a complete binary tree, Fig. 3) could not be confirmed.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.