BioSysBio:abstracts/2007/Naoki Matsumaru/AppendixB

Algorithm to design reaction network to solve the maximal independent set problem

Let an undirected graph [math]\displaystyle{ G=\langle V, E \rangle }[/math] be defined by a set of [math]\displaystyle{ N }[/math] vertexes [math]\displaystyle{ V=\{v_1, \dots, v_{N}\} }[/math] and a set of edges [math]\displaystyle{ E }[/math]. When two vertexes [math]\displaystyle{ v_p }[/math] and [math]\displaystyle{ v_q }[/math] are connected, the pair of the vertexes are in the set: [math]\displaystyle{ (v_p,v_q)\in E }[/math]. Note that the order of the pair is insignificant, that is, [math]\displaystyle{ (v_p,v_q)=(v_q,v_p) }[/math]. Given the undirected graph [math]\displaystyle{ G }[/math], an algebraic chemistry [math]\displaystyle{ \langle {\mathcal M},{\mathcal R} \rangle }[/math] is designed as follows. For each vertex [math]\displaystyle{ v_j }[/math], we assign two molecular species [math]\displaystyle{ s_j^0 }[/math] and [math]\displaystyle{ s_j^1 }[/math] 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 [math]\displaystyle{ s_j^1 }[/math] means that the vertex [math]\displaystyle{ v_j }[/math] is included in the maximal independent set. High concentration of species [math]\displaystyle{ s_j^0 }[/math] represents that the vertex [math]\displaystyle{ v_j }[/math] is not included in the maximal independent set. Thus the set of molecular species [math]\displaystyle{ {\mathcal M} }[/math] contains [math]\displaystyle{ 2N }[/math] molecular species:

[math]\displaystyle{ {\mathcal M}=\{s_{j}^0,s_{j}^1\; |\; j=1,\dots,N\} }[/math]

The set of reaction rules [math]\displaystyle{ {\mathcal R} }[/math] is constructed by assembling reactions for each vertex:

[math]\displaystyle{ {\mathcal R} = \bigcup_{i=1}^N {\mathcal R} ^i, }[/math]

and for each reaction set [math]\displaystyle{ {\mathcal R} ^i }[/math], there are three sorts of reactions:

[math]\displaystyle{ {\mathcal R}^i = ({\mathcal V}^i \cup {\mathcal N}^i \cup {\mathcal D}^i) }[/math]

The first is a reaction rule to produce species [math]\displaystyle{ s_i^1 }[/math]:

[math]\displaystyle{ \begin{matrix} {\mathcal V}^i =(&\underbrace{s_h^0 + s_k^0 + \dots + s_l^0}& \to n_i s_i^1)\\ &n_i&\\ \end{matrix} }[/math]

where [math]\displaystyle{ n_i }[/math] is the number of vertexes connected to vertex [math]\displaystyle{ v_i }[/math] and [math]\displaystyle{ v_h, v_k, \dots, v_l }[/math] are these neighboring vertices, that is, [math]\displaystyle{ (v_i, v_h), (v_i, v_k), \dots, (v_i, v_l) \in E }[/math]. The left hand side of the reaction contains [math]\displaystyle{ n_i }[/math] terms, and this reaction is interpreted as follows: When no neighboring vertex is included in the maximal independent set, the target vertex [math]\displaystyle{ v_i }[/math] should be included in the set.

The negation of this predicate is considered by a set of [math]\displaystyle{ n_i }[/math] reactions:

[math]\displaystyle{ {\mathcal N}^i = \{s_j^1 \to s_i^0 | (v_i,v_j)\in E\}. }[/math]

This is the second type of the reactions, which produce species [math]\displaystyle{ s_i^0 }[/math] from any species corresponding to the neighboring vertexes with superscript [math]\displaystyle{ 1 }[/math]. 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 [math]\displaystyle{ v_i }[/math] should be excluded from the maximal independent set (otherwise the definition of the maximal independent set would be violated). Generating species [math]\displaystyle{ s_i^0 }[/math] forces vertex [math]\displaystyle{ v_i }[/math] 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 [math]\displaystyle{ {\mathcal R} ^i }[/math] 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:

[math]\displaystyle{ {\mathcal D}^i = s_{i}^0 + s_{i}^1 \to \emptyset. }[/math]