Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process

The multi-type Moran process is an evolutionary process on a connected graph G in which each vertex has one of k types and, in each step, a vertex v is chosen to reproduce its type to one of its neighbours. The probability of a vertex v being chosen for reproduction is proportional to the fitness of the type of v . 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 fixation probability , i.e., the probability that eventually all vertices are mutants. 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 absorption time , i.e., the time that it takes the multi-type Moran process to reach a state in which each vertex has the same type.