| Achoimre: | <p>The multi-type Moran process is an evolutionary process on a connected graph <em>G</em> in which each vertex has one of <em>k</em> types and, in each step, a vertex <em>v</em> is chosen to reproduce its type to one of its neighbours. The probability of a vertex <em>v</em> being chosen for reproduction is proportional to the fitness of the type of <em>v</em>. So far, the literature was almost solely concerned with the 2-type Moran process in which each vertex is either healthy (type 0) or a mutant (type 1), and the main problem of interest has been the (approximate) computation of the so-called <em>fixation probability</em>, i.e., the probability that eventually all vertices are mutants.</p>
<p>In this work we initiate the study of approximating fixation probabilities in the multi-type Moran process on general graphs. Our main result is an FPTRAS (fixed-parameter tractable randomised approximation scheme) for computing the fixation probability of the dominant mutation; the parameter is the number of types and their fitnesses. In the course of our studies we also provide novel upper bounds on the expected <em>absorption time</em>, i.e., the time that it takes the multi-type Moran process to reach a state in which each vertex has the same type.</p>
|
|---|