Detecting Attractors in Biological Models with Uncertain Parameters 43We may also sometimes be interested in certain simpler versions of the prob-
lem. In thecounting version, we are only interested in the number of tSCCs,
i.e. we want to compute the functionc:P→Nthat assigns to each parameter
valuationpthe number of tSCCs inGp.Inthethresholdversion, we are given
a threshold number of tSCCs and want to partition the set of parameter valu-
ationsPinto those for whichGpcontains at least the given number of tSCCs
and those for which it does not. Finally, in theexistential thresholdversion, we
only aim to decide whether there exists a parameter valuationpfor whichGp
contains at least the given number of tSCCs.
2.1 Algorithm
Our goal is to develop a parallel (shared-memory or distributed-memory) algo-
rithm for solving the tSCCs Detecting Problem. A simplesequential solution
to the problem is to use any reasonable SCC decomposition algorithm (e.g.
Tarjan’s [ 25 ]) and enumerate the terminal components in the residual graph.
However, all known optimal sequential SCC decomposition algorithms use the
depth-first search algorithm, which is suspected to be non-parallelisable [ 22 ].
There are known parallel SCC decomposition algorithms; for a survey we refer
to [ 1 ]. Our approach here, however, is based on the observation that we do not
have to compute all the SCCs in order to enumerate the terminal ones. Fur-
thermore, instead of scanning through all parameter valuations and solving the
problem for every one of them separately our approach deals with sets of parame-
ter valuations directly. This makes our algorithm suitable for use in connection
with various kinds of symbolic set representations.
F\BBB′\FV\B′vFig. 1.Illustration of the non-parametrised version of our algorithm.The main idea of the Terminal Component Detection (TCD) algorithm lies in
repeated reachability, which is known to be easily parallelisable. To explain the