  Evolutionary graph theory studies the evolutionary dynamics in a population
structure given as a connected graph. Each node of the graph represents an
individual of the population, and edges determine how offspring are placed. We
consider the classical birth-death Moran process where there are two types of
individuals, namely, the residents with fitness 1 and mutants with fitness r.
The fitness indicates the reproductive strength. The evolutionary dynamics
happens as follows: in the initial step, in a population of all resident
individuals a mutant is introduced, and then at each step, an individual is
chosen proportional to the fitness of its type to reproduce, and the offspring
replaces a neighbor uniformly at random. The process stops when all individuals
are either residents or mutants. The probability that all individuals in the
end are mutants is called the fixation probability. We present faster
polynomial-time Monte-Carlo algorithms for finidng the fixation probability on
undirected graphs. Our algorithms are always at least a factor O(n^2/log n)
faster as compared to the previous algorithms, where n is the number of nodes,
and is polynomial even if r is given in binary. We also present lower bounds
showing that the upper bound on the expected number of effective steps we
present is asymptotically tight for undirected graphs.
