# BioSysBio:abstracts/2007/Naoki Matsumaru/AppendixB

### From OpenWetWare

## 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 *v*_{p} and *v*_{q} are connected, the pair of the
vertexes are in the set: . Note that the order of the
pair is insignificant, that is, (*v*_{p},*v*_{q}) = (*v*_{q},*v*_{p}).
Given the undirected graph *G*, an algebraic chemistry is
designed as follows.
For each vertex *v*_{j}, 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 *v*_{j} is
included in the maximal independent set.
High concentration of species
represents that the vertex *v*_{j} is
*not* included in the maximal independent set.
Thus the set of molecular species contains 2*N* 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 *n*_{i} is the number of vertexes connected to vertex *v*_{i} and
are these neighboring vertices, that is,
.
The left hand side of the reaction contains *n*_{i} terms, and
this reaction is interpreted as follows:
When no neighboring vertex is included in the maximal independent set,
the target vertex *v*_{i} should be included in the set.

The negation of this predicate is considered by a set of
*n*_{i} 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 *v*_{i} should be excluded from the maximal
independent set (otherwise the definition of the maximal independent
set would be violated).
Generating species forces vertex *v*_{i} 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: