Fixation times in Moran process on directed graphs

Introduced in 1958 in the field of population genetics, Moran process is a stochastic process that models the long-term fate of a newly occurring mutation, as it attempts to spread through a population of reproducing individuals. The spatial structure of the population can be represented by a graph, where nodes correspond to individuals and edges to their interactions. The Moran process then changes the vertex coloring of the graph, one vertex at a time. Eventually, the mutants either take over the whole graph, an event called fixation, or they disappear completely.

The two most studied quantities are the fixation probability of the new mutant, and the fixation time, that is, the expected number of steps until the process terminates. Both quantities critically depend on the graph structure and are believed to be hard to compute exactly for arbitrary graphs. In 2014, Diaz, Goldberg, Mertzios, Richerby, Serna, and Spirakis showed that for any undirected graph the fixation time is polynomially short, and thus fixation probability can be efficiently approximated by simulations. We consider directed graphs. We present an upper bound for the fixation time, and we show that this upper bound is polynomial for a broad class of directed graphs that includes most families of directed graphs that were previously studied in the context of Moran process.