In order to present the problem and its respective solution in a coherent fashion, some concepts that will be use used in this chapter need to be presented. Given a connected graph G and two nodes v and u, which belong to G, if an edge e connects v and u, then v and u are neighbors. This implies that they have a relation of adjacency. If two nodes are neighbors in G and D results from an orientation of G, then those two nodes are also neighbors in D, regardless of the orientation of the edges. The reverse of an orientated edge e from v to u is an orientated edge f from u to v.
For the graph contamination problem, nodes of a graph C are in one of three states: contaminated, clean, and guarded or clean. Contaminated is the initial state of all nodes. A (clean and) guarded node is a node that has received a decontamination agent, which is a tool of the decontamination algorithm and can have different properties regarding creation of new agents and mobility. After leaving a node, the decontamination agent becomes clean. If a clean node has a contaminated neighbor, it becomes contaminated again. This event is called recontamination.
A sink decomposition is a distribution of the nodes of an acyclic connected digraph D in numbered layers. The layer of a node is the length of the longest simple path to any sink, or zero if the node is itself a sink. This also results in the property that a node in layer k, for 1 ≤ k ≤ l, where l is the highest layer, has always at least one neighbor in layer k – 1.