Algorithm to design reaction network to solve the maximal independent set problem
Let an undirected graph be defined by a set of N vertexes and a set of edges E. When two vertexes vp and vq are connected, the pair of the vertexes are in the set: . Note that the order of the pair is insignificant, that is, (vp,vq) = (vq,vp). Given the undirected graph G, an algebraic chemistry is designed as follows. For each vertex vj, we assign two molecular species and representing the membership of the vertex in the maximal independent set. The subscript of the species name corresponds to the index number of the vertex. High concentration of species means that the vertex vj is included in the maximal independent set. High concentration of species represents that the vertex vj is not included in the maximal independent set. Thus the set of molecular species contains 2N molecular species:
The set of reaction rules is constructed by assembling reactions for each vertex:
and for each reaction set , there are three sorts of reactions:
The first is a reaction rule to produce species :
where ni is the number of vertexes connected to vertex vi and are these neighboring vertices, that is, . The left hand side of the reaction contains ni terms, and this reaction is interpreted as follows: When no neighboring vertex is included in the maximal independent set, the target vertex vi should be included in the set.
The negation of this predicate is considered by a set of ni reactions:
This is the second type of the reactions, which produce species from any species corresponding to the neighboring vertexes with superscript 1. This rule can be interpreted as follows: If there exists at lease one neighboring vertex included in the maximal independent set, then the target vertex vi should be excluded from the maximal independent set (otherwise the definition of the maximal independent set would be violated). Generating species forces vertex vi not to be included in the set. In passing note that two predicates constitute a program for any distributed processor to solve the maximal independent set problem under a central scheduler.
The last component of set is a destructive reaction. Since the membership of the maximal independent set is a binary state, the state becomes undefined when neither or both of the species are present. In order to avoid the latter case, the two opposite molecular species are defined to vanish upon collision: