  We consider the classic Moran process modeling the spread of genetic
mutations, as extended to structured populations by Lieberman et al.\ (Nature,
2005). In this process, individuals are the vertices of a connected graph $G$.
Initially, there is a single mutant vertex, chosen uniformly at random. In each
step, a random vertex is selected for reproduction with a probability
proportional to its fitness: mutants have fitness $r>1$, while non-mutants have
fitness 1. The vertex chosen to reproduce places a copy of itself to a
uniformly random neighbor in $G$, replacing the individual that was there. The
process ends when the mutation either reaches fixation (i.e., all vertices are
mutants), or gets extinct. The principal quantity of interest is the
probability with which each of the two outcomes occurs.
  A problem that has received significant attention recently concerns the
existence of families of graphs, called strong amplifiers of selection, for
which the fixation probability tends to 1 as the order $n$ of the graph
increases, and the existence of strong suppressors of selection, for which this
probability tends to 0. For the case of directed graphs, it is known that both
strong amplifiers and suppressors exist. For the case of undirected graphs,
however, the problem has remained open, and the general belief has been that
neither strong amplifiers nor suppressors exist. In this paper we disprove this
belief, by providing the first examples of such graphs. The strong amplifier we
present has fixation probability $1-\tilde O(n^{-1/3})$, and the strong
suppressor has fixation probability $\tilde O(n^{-1/4})$. Both graph
constructions are surprisingly simple. We also prove a general upper bound of
$1-\tilde \Omega(n^{-1/3})$ on the fixation probability of any undirected
graph. Hence, our strong amplifier is existentially optimal.
