EFTA01139453.pdf

l het CrossMark Computational complexity of ecological and evolutionary spatial dynamics Rasmus Ibsen-lensenbi, Krishnendu Chatterjeeb, and Martin A. Nowakb °Institute of Science and Technology Austria, A-3400 Klosterneuburg, Austria; and °Program for Evolutionary Dynamics, Departments of Organismic and Evolutionary Biology and Mathematics, Harvard University, Cambridge, MA 02138 Edited by Christos Papadimitriou, University of California, Berkeley, CA. and approved November 10, 2015 (received for review June 10, 201S) There are deep, yet largely unexplored, connections between by modifying the fixation probability. The classic studies of computer science and biology. Both disciplines examine how Maruyama (2) and Slatkin (3) showed that symmetrical pop- information proliferates in time and space. Central results in ulation structures, such as regular lattices, do not change the computer science describe the complexity of algorithms that solve fixation probability compared with the well-mixed population. certain classes of problems. An algorithm is deemed efficient if it can The effect of population structure on evolution is also at the solve a problem in polynomial time, which means the running time of heart of the famous Wright-Fisher debate (4-6). the algorithm is a polynomial function of the length of the input. There In 2005, evolutionary graph theory was introduced as a tool to are classes of harder problems for which the fastest possible algorithm study how generalized population structures affect evolutionary requires exponential time. Another criterion is the space requirement outcome (7), and it has been studied in many other works (8-12). The individuals occupy the vertices of the graph. The links (edges) of the algorithm. There is a crucial distinction between algorithms determine who interacts with whom for receiving payoff and for that can find a solution, verify a solution, or list several distinct reproduction. There can be a single graph for game dynamical in- solutions in given time and space. The complexity hierarchy that is teraction and evolutionary replacement, or the interaction and re- generated in this way is the foundation of theoretical computer placement graphs can be distinct (13). Often, the graph is held science. Precise complexity results can be notoriously difficult. The constant during evolutionary updating, but it is also possible to famous question whether polynomial time equals nondetenninistic study dynamically changing graphs (14-22). The original Moran polynomial time 0.e., P = NP) is one of the hardest open problems in process is recovered as a special case given by the complete graph. computer science and all of mathematics. Here, we consider simple It turns out that all isothermal graphs. where all vertices have the processes of ecological and evolutionary spatial dynamics. The basic same rate of updating (the same "temperature"), have the same question is: What is the probability that a new invader (or a new fixation probability as the well-mixed population (7). All symmet- mutant) will take over a resident population? We derive precise com- rical population structures lead to isothermal graphs, but the con- plexity results for a variety of scenarios. We therefore show that verse is not true. some fundamental questions In this area cannot be answered by Many evolutionary contests, however, are not fought out with simple equations (assuming that P Is not equal to NP). constant fitness. Instead, the fitness of individual types depends on the frequency (is, relative abundance) of types in the pop- evolutionary games I fixation probability I complexity classes ulation. A well-known approach to frequency-dependent selection is evolutionary game theory (23-27). Here, the fitnesses of in- dividuals are linear functions of the frequencies. The coefficients E volution occursin populations of reproducing individuals. Mutation generates distinct types. Selection favors some types over others. The mathematical formalism of evolution de- of the linear function are the elements of the payoff matrix. Again, constant selection is a special case of frequency-dependent selection; for constant selection, all entries in a row of the payoff scribes how populations change in their genetic (or phenotypic) matrix are the same and this property holds for all rows. Evo- composition over time. Deterministic models of evolution are based lutionary game theory has traditionally been investigated with on differential equations. They assume infinitely large population size and ignore demographic and other stochasticity. The more Significance precise descriptions of evolutionary dynamics, however, use sto- chastic processes, which take into account the intrinsic randomness An important question in evolution is: how does population of when and where individuals reproduce and how many of their structure affect the outcome of the evolutionary process? The offspring survive. They also describe populations of finite size. theory of evolution in structured population has provided an A well-known stochastic process of evolution was formulated impressive range of results, but an understanding of the com- by Moran in 1958 (1). In any one-time step, a random individual putational complexity of even simple questions was missing. We is chosen proportional to fitness for reproduction and a random individual is chosen for death. The offspring of the first indi- prove that some fundamental problems in ecology and evolution vidual is added to the population. The total population size re- can be precisely characterized by well-established computational mains constant and is given by N. The original process was complexity classes. This implies that the problems cannot be formulated for constant fitness, which means the fitness value of answered by simple equations. For example, there cannot be individuals does not depend on the relative abundance of various simple formulas for the fixation probability of a mutant given types in the population; it is a fixed number. The crucial question frequency-dependent selection in a structured population. is: What is the probability that a newly introduced mutant will We also show that, for example, calculating the molecular generate a lineage that takes over the entire population? This clock of neutral evolution in structured populations admit quantity is called the fixation probability. For the original Moran efficient algorithmic solutions. process, there is a simple formula. If the resident has fitness 1 and the mutant has fitness r, then the fixation probability of the Author contributions: LC. and MAN. designed research performedresearch, and mutant is given by p= (1 — 1/r)/(1 — 1/rw). wrote the paper. The Moran process assumes that the biological population is The author declare no conflict of interest. well mixed. The offspring of any one individual can replace any This article Is a PNAS Direct Submissica. other individual. If there is a spatial or social population struc- 'To whom correspondence should be addressed. Email: ribseninst ac et ture, then such is not the case. The question arises as to which This article contains supportin information online at v.ww.pnas.orgilcokuprsupplidoi:10. population structures affect the outcome of evolution, for example, I073/tinat. 1511366f IZNIX5uPPlernentat www.poeS.0rg/Cgild0i/10.107344MS.15I B66112 PNAS Early Edition I 1 of 6 EFTA01139453 deterministic equations describing infinitely large populations problem P2, is a translation such that a solution for P2 can provide (23-26) and, more recently, has moved to finite population size a solution for Pi. More precisely, if there is a polynomial-time and stochastic processes (27-38). reduction from Pr to P2, then a polynomial-time algorithm for P2 Evolutionary games have a long history of being studied on implies a polynomial-time algorithm for Pi. spatial lattices (28, 39-42) and, more recently, on graphs (7, 27, 43, A given problem is NP-hard if for every problem in NP, there 44). The crucial quantity that needs to be calculated to evaluate is a polynomial reduction to the given problem. A problem is NP- natural selection is the fixation probability, p, of a newly introduced complete if it is both NP-hard and there is an NP algorithm for mutant that arises at a random position on the graph. If p > 1/N, the problem. where N is the population size, then natural selection favors the For example, consider a Boolean formula over variables, and fixation of the new mutant, because a neutral mutant would have a the question of whether there exists an assignment to the vari- fixation probability of I/N. In a contest between two strategies, ables such that the formula is true. A polynomial candidate so- another question would be if the fixation probability of the first lution is an assignment of truth values to variables, and given a strategy exceeds the fixation probability of the second strategy. If candidate assignment, the formula can be evaluated in poly- such is the case, then the first strategy would be more abundant in nomial time. This question is the famous satisfiability (SAT) mutation-selection equilibrium for low mutation rate. The crucial problem in computer science. The SAT problem is NP-complete. problem is of the following form: Given a graph and a payoff The class P is contained in NP, and a major long-standing open matrix, what are the fixation probabilities of an individual of a new question in computer science is whether P = NP. A polynomial- type arising in a population of the other type? time algorithm for an NP-complete (or an NP-hard) problem would Spatial structure plays an important role in many cases. For imply that P = NP, resolving the long-standing open problem. example, spatial structure can affect the rate of neutral evolution 'Ile class sharp (# P) intuitively corresponds to counting the (45), and there are results that describe which spatial structures number of solutions. A problem is in # P if it counts the number do or do not affect the outcome of constant selection (46-48). of distinct solutions such that (i) every possible candidate for a Some population structures can be amplifiers or suppressors of solution is of polynomial length, and (ii) given a candidate for a constant selection (7, 49, 50), meaning that they modify the in- solution, it can be checked in polynomial time whether the candi- tensity of selective differences. Finally, for evolutionary games, date is a solution. For example, given a Boolean formula, the spatial structure can favor evolution of cooperation (28, 51). problem of whether there are at least k distinct satisfying assign- The study of spatial dynamics also has a long tradition in ments to the formula is a # P-problem. A given problem is ecology (52-56). Here, the typical setting is that different species # P-hard, if for every # P-problem, there is a polynomial-time re- compete for ecological niches. Many evolutionary models are duction to the given problem. A # P-complete problem is a problem formally equivalent to ecological ones, especially if we consider that is both # P-hard and for which there is a # P-solution. For only selection and not mutation. Then we can interpret the dif- example, counting the number of solutions in SAT is # P-oomplete. ferent types of evolutionary games as different species. Again, a The class NP is contained in # P because, given the enumer- crucial question is: What is the probability that a newly introduced ation of solutions for # P, it is easy to check if there exists at least species can get established or take over an ecological niche? one solution. Intuitively, an NP problem asks whether there is at This paper is structured as follows. First, we give an intuitive ac- least one solution, whereas # P is the counting version that asks count of the foundation of theoretical computer science. We de- if there are least k distinct solutions (and the special case ofIt =I scribe classes of problems that can be solved by algorithms in certain gives NP). Again, a major open question is whether NP = # P. time and space constraints. Subsequently, we present two simple Note that a polynomial-time algorithm for a # P-complete problems of evolutionary dynamics in spatial settings. The first problem would be an even bigger result, because it would imply problem is motivated by a very simple ecological dynamic: the sec- both P = NP and P = # P. ond problem is the general setting of evolutionary games on graphs. The class PSPACE consists of problems that can be solved with In both (-Agog the basic question is to calculate the takeover prob- polynomial space. Note that a polynomial space algorithm can ability (or fixation probability) of a new type. That is. we introduce a reuse space and can, in general, require exponential time. Every new type in a random position in the population, and we ask what is # P problem can be solved in PSPACE by simply enumerating the complexity of an algorithm that can characterize the probability each candidate for a solution and checking if it is a solution. Because that the new type takes over the population (becomes fixed). Un- we can reuse space to enumerate the candidates for solutions, the expectedly, we are able to prove exact complexity, results (Table 1). enumeration can be achieved in polynomial space. Moreover, The class PTIME (denoted as P) consists of problems whose every polynomial-time algorithm uses, at most, polynomial space. solutions can be computed by an algorithm that uses polynomial Hence, it follows that # P is contained in PSPACE. The notion of time. Formally, an algorithm uses polynomial time if the running PSPACE-hardness and PSPACE-completeness is similar to the time of the algorithm grows as a polynomial function of the size of notion of NP-hardness and NP-completeness, but with respect to the input. In computer science, P represents the class of problems the problems in PSPACE. Again, a long-standing open question in that can be solved efficiently. computer science is whether #P = PSPACE, and a polynomial- The class nondeterministic polynomial time (denoted as NP) time algorithm for a ['SPACE-complete (or ['SPACE-hard) consists of problems for which solutions exist that are of polynomial problem would imply P = NP = # P = PSPACE. length. and given a candidate for a solution of polynomial length, We have mentioned that the major questions about the equality whether the candidate is indeed a solution can be checked in of the complexity classes are open problems, but the widely be- polynomial time. Therefore, an NP algorithm can verify a solution lieved conjecture is that P is strictly contained in NP, NP is strictly in polynomial time. contained in # P, and # P is strictly contained in PSPACE. To proceed further, we need the notion of "reduction" between In other words, it is widely believed that NP-complete problems classes of problems. A reduction, from a given problem Pi to a cannot be solved in polynomial time, # P-complete problems are harder than NP-complete problems, and ['SPACE-complete problems are harder than # P-complete problems. A pictorial Table 1. Complexity results for various models and illustration of the complexity classes is shown in Fig. I. computational questions Results Model Qualitative Quantitative The first problem is motivated by ecological dynamics. There is Ecological scenario NP-complete N P-complete an ecosystem occupied by resident species. The spatial structure Linear fitness PSPACE-complete PSPACE-complete of the ecosystem is given by a graph. An invading species is in- Exponential fitness P PSPACE-complete troduced (an illustration is provided in Fig. 2). We assume the invading species has a competitive advantage in the sense that 2 of 6 I www.pnes.agfegilda/10.10734,natISI1366112 Ibsen-Jensen et al. EFTA01139454  We are interested in the probability that a single A individual starting in a random position on the graph generates a lineage that will take over the entire population; this probability is generally called fixation probability. As before, there are two types of ques- tions. The qualitative question is whether the fixation probability is positive. The quantitative question is concerned with computing the Fig. I. Pictorial illustration of the complexity classes P, NP, a P, and PSPACE. The o complexity class P is contained in NP, NP is contained in 0 P, and I P is contained in PSPACE. The widely believed conjecture is that these complexity classes are * different. A problem is NP-hard if it is at least as hard as each problem in NP, and the case is similar for a P-hardness and PSPACE-hardness. The intersection of NP and NP-hard gives the NP-complete problems, the intersection of fl P and a P-hard gives the I P-complete problems, and the intersection of PSPACE and PSPACE-hard gives the PSPACE-complete problems. A polynomial-time solution for an NP-hard or NP-complete problem would imply P = NP. once a position is occupied by the invading species, the resident cannot get it back. The invading species, however, has a density constraint: If the number of invaders around a focal invader is Qt: Probability >IR above a threshold, it, then the invader in the focal vertex cannot Q2: Appracimate probability? colonize another vertex. We are interested in the probability that the invader starting from a random initial position will take over the entire ecosystem (and therefore drive the resident to extinction). There are two types of questions The "qualitative question- is whether the takeover prob- ability is greater than 0. The "quantitative question- is concerned with computing the takeover probability subject to a small enor. Fig. 2 gives a pictorial illustration. We prove the following results. The qualitative question is NP-complete (SI Appendir, Theorem 4). The quantitative question is # P-complete (SI Appendix, Theorem 8). The second problem is concerned with evolutionary games in structured populations. There are two types, A and B, whose reproductive rates depend on local interactions. We consider the setting of games on graphs. Each vertex is occupied by one in- dividual, which is either A or B. Interactions occur pairwise with all neighbors. The payoff matrix is given by Fig. 2. Illustration of mutant introduction. The residents (type A) are col- ored blue, and the mutants (type 8) are colored red. The black edges are the A B edges of the interaction graph and the red edges are the edges of the re- A la b\ production graph. The probability of introducing a mutant in a specific Ill vertex is always 1 over the number of vertices. The computational questions B kc di' of interest regarding the takeover probability are as follows: whether the probability is positive (qualitative question) and what is an approximation of The entries of the payoff matrix can be positive or negative (or the probability (quantitative question). 0). Each individual interacts with all of its neighbors on the graph to derive a payoff sum. The payoff sum is translated into repro- ductive success as follows. If the payoff sum is positive, then the fixation probability subject to a small error. We prove the following fecundity equals the payoff sum. If the payoff sum is negative, results. The qualitative question is NP-hard and in PSPACE. The then the fecundity is 0. We refer to this translation as linear quantitative question is # P-hard and in PSPACE. The results fitness. In any one time step, a random individual is chosen for follow from SI Appendir, Theorems 4. 8, and 15. reproduction proportional to its fecundity. The offspring, which Note that the first problem can also be obtained as a special is of the same type as the parent, is placed into an adjacent case of the second problem. In the payoff matrix (1), we can set, position on the graph (illustrations are provided in Figs. 3 and 4). for example, a =-1, b =1,c =d= O. This "game- has the property Ibsen-lensen et al. PNAS Fatty Edition I 3 of 6 EFTA01139455  We also consider a variation of the second problem. In par- ticular, we change the mapping from payoff to fecundity. We now assume that fecundity is an exponential function of payoff, and refer to it as exponential fitness (an illustration is provided in Fig. 4). Therefore, the fecundity of an individual is always positive (even if its payoff sum is negative). In this setting, the qualitative question can be decided in polynomial time. The reason is that the IA fixation probability is positive if the graph is connected. Thus, to answer the qualitative question, the algorithm only needs to check whether the graph is connected; this problem is in P. However, the VA quantitative question has the same complexity as the previous problem (SI Appendix, Theorems 16 and 17). a A very special case of games on graphs is constant selection. Type A has constant fecundity a and type B has constant fecundity b independent of any interactions (i.e., fecundity is independent of the population structure). The qualitative question concerning the fixation probability of A is in P. The quantitative question is in PSPACE, but any nontrivial lower bound is an open question. Finally, although we establish computational hardness for sev- eral problems, we also show that two classic problems can be solved in polynomial time (SI Appendix, section 7). First, we consider the molecular clock, which is the rate at which neutral mutations ac- cumulate over time. The molecular clock is affected by population structure (13). We show that the molecular clock can be computed in polynomial time because the problem reduces to solving a set of linear equalities, which can be achieved in polynomial time using Gaussian elimination. Second, we consider evolutionary games in a well-mixed population structure, where the underlying structure is the complete graph (38). We show that the exact fixation proba- bility can be computed in polynomial time. In this case the prob- lem can be reduced to computing absorption probabilities in Markov chains, where each state represents the number of mu- tants. Hence, the Markov chain is linear in the number of vertices of the graphs, and because absorption probabilities in Markov chains can be computed in polynomial time (by solving a set of linear equalities), we obtain the desired result. Methods: Proof Ideas We now present the key intuition and main ideas of our results. The most interesting and technically insightful results are the lower bounds (ii.e., the hardness proofs), and we present the key ideas only for them. NP-Hardness of the Qualitative Ecological Problem. One of the most classic he- complete problems is the 3SAT-problem. whidy is the SAT problem where every dause has exactly three literals (a literal is a Boolean variable x or a negation of a a a variable x). Given instances of the 3SAT problem, we construct itstances of the Sg. 3. Illustration of reproduction with matrix a ( e ) . The residents ecological problem where we have a start vertex, where the mutant arises, fol- lowed by a sequence of vertices fie., each vertex can reproduce a mutant to the (type A) are colored blue, and the mutant (type 8) afe adored red. The black next), one for each dause. By means of mg construction, a vertex in this sequence edges are the edges of the interaction graph, and the red edges are the can reproduce, at most, three times, one of which must be the next vertex of the edges of the reproduction graph. In the first figure beside each vertex, the payoff sequence, with the others corresponding to, at most, two literals of the clause of the vertex (which is the sun of the payoff of the interactions) is shown. Because (intuitively, these two literals represent the ones that are not set to true by a the first figure shows the payoff computation, the interaction edges that are re- candidate-satisfying assignment). The last vertex of the sequence reproduces to a sponsible for the payoff calculation are boldfaced. In the second figure, the vertex new sequence of vertices that corresponds to an assignment of truth values to the labeled 3 is selected for reproduction. The reproduction edges from vertex 3 are variables. Each vertex in this new sequence can reproduce twice, one to the next bddfaced and each edge has the probability 1/2. Finally, the successor S is chosen vertex of the sequence and other to a variable or its negation. The variables or the for replacement (i.e. vertex 3 reproduces to vertex 5). corresponckm negation can then reproduce mutants to the corresponding literals of the clauses. After this sequence, all vertices that do not correspond to a literal in a clause become mutants. In essence, our construction ensures that if there is that type B never reproduces and type A reproduces until half of a satisfying assignment then with positive probability, all vertices can become its neighbors are also of type A. This parameter choice leads to mutant, and conversely. if there is no satisfying assignment then the proba- the same qualitative behavior and the same complexity bounds as bility that all vertices become mutants is O. described in the first problem. A generalization of games on graphs is the setting where the Madness of the Quantitative Ecologkal Problem. A Y P-complete problem interaction graph and the replacement graph are distinct (13). is counting the number of perfect matthings in a bipartite graph (which also Thus, each individual interacts with all of its neighbors on the corresponds to computing the permanent of a Boolean matrix). A bipartite graph consists of two set of vertices, a set on the left side arid a set on the interaction graph to receive payoff. Subsequently, an individual right side, with edges from the left side to the right side. A perfect matching is chosen for reproduction proportional to its fecundity. The off- is a one-to-one mapping of each vertex of the left side to a vertex on the spring is placed randomly among all neighbors of the focal indi- right side such that there is an edge between them. First, we argue that for vidual on the replacement graph. In this case, both the qualitative the hardness proof, it suffices to consider bipartite graphs in which each and quantitative questions become PSPACE-complete (S1 Ap- vertex on the left side has an out-degree of 2v for some integer k. A key idea pendix, Theorem 15). in our construction is that in a full binary tree, if the root becomes a mutant 4 of 6 I wwwonts.orgfcgildoi/10.1073/6nas.1511366112 Ibsen-Jensen et al. EFTA01139456  Peve eq144.161 &lino now Fig. 4. Illustration of different payoffs to fitness A with A ( -I z II . The residents (type A) are blue. -2 and themutants (type B) are red. The black edges are the edges of the interaction graph, and the red edges are the edges of the reproduction graph. In the fgure of the first row, we show the payoff for every vertex_ ki the next row, we show the fitness, which is either a linear function of the payoff but at least 0 or an n4•111,. exponential function of the payoff. Finally, in the thid row, with each vertec we show the mobabikty, which is the normalized fitness, that the vertex is selected for reproduction fin the last figure. the number xis the sum of the fitness x =e2 +2e+ 2ei and every vertex can reproduce exactly once, then the set of mutants will dynamics in structured populations. Our main results are summa- eventually consist of a path from the root to a leaf, chosen uniformly at rized in Table 1. We now discuss the significance of our findings. random. Our construction is then as follows: We have a start vertex where the mutant arises, which reproduces to turn each of the vertices on the left interdisdplinary Connection. Although both computer science and side of the bipartite graph to mutants. Each of the vertices on the left side is biology examine the proliferation of information in time and space, the root of a full binary tree, where the leaves correspond to the right side the deep connection between them has been largely unexplored. of the bipartite graph. We show that the fixation process corresponds to a Our work provides precise computational complexity insults for perfect matching (defined from the path in the full binary trees), and given several well-studied problems in biology and can be viewed as a step an approximation of the fixation probability, the exact number of perfect to establish a connection between the two disciplines. matchings of the bipartite graph can be computed. Well-Studied Open Problem. The problems we have considered are PSPACE-Hardness for the Game on Evolutionary Graph Problem. Our PSPACE- hardness proof shows that the evolutionary process can solve the following basic aspects of well-studied questions for ecological and evo- concurrent-if problem, which we show is PSPACE-hard. The concurrent-if lutionary dynamics in structured populations (7, 28, 37, 42, 50, problem consists of a set of Boolean variables xi,x2, ,x,,, with a given 51). Several reviews have been written on this topic (8, 11, 43, initial truth assignment to the variables, and a set of if-statements. Each if- 57). We first discuss the significance of an algorithmic approach statement s, is of the following form: If a conjunctive clause C, over the in evolutionary graph theory. An efficient algorithm, which con- variables is true, then assign a truth value to a variable (e.g„ if (xinx.nis), siders all (even worst-case) graphs for evolutionary processes, is then xi is assigned false). The problem is to decide whether the first variable important for the following reasons. (Which is the accepting variable) eventually becomes true. We show that First, it has been shown that some population structures each variable can be represented as four vertices, and each if-statement as a (called amplifiers) can increase the effect of natural selection single vertex, in the evolutionary graph and the evolutionary process can (7,51), but amplifiers are rare and constructing them is difficult (7, mimic the execution of the concurrent-if problem. Finally, if the accepting 11, 50, 51, 58, 59). If there were an efficient algorithmic approach variable becomes true, then it corresponds to making a special vertex in the that worked for all graphs, then one could design candidates for evolutionary graph as a mutant. There exists a part of the evolutionary amplifiers and efficiently check their fixation probabilities. Be- graph that can only become mutants after the special vertex has become a cause there exists no algorithmic approach, research has to focus mutant. Using this construction, we show that both the qualitative and on special classes of graphs to identify simple formulas, such as quantitative problems are PSPACE-hard for evolutionary games on graphs. calculating the fixation probabilities on star-like graphs (58). Second, it is known that some population structures and evo- Discussion lutionary dynamics promote evolution of cooperation but that In summary, we have established computational complexity results others do not (51). An important open problem is to characterize for some fundamental problems of ecological and evolutionary the set of graphs that promote cooperation. An efficient algorithmic Ibsen-Jensen et al. PNAS Early Edition I 5 of 6 EFTA01139457 approach would be useful to check candidate structures. Because widely believed conjecture that P is different from NP. A simple no efficient algorithm exists, one has to study special cases, for equation-based solution would give an efficient algorithm; thus, our example, by considering nearly regular graphs (51). result formally shows that for evaluating the fixation probability in Thus, a general algorithmic approach is a very important problem spatial settings there does not exist a simple equation-based solu- for the well-studied question concerning the effect of population tion in general. Our results are significant for the following reasons: structures on evolutionary dynamics. An algorithmic approach has (1) They establish the computational complexity for fundamental been studied for important special cases, such as for complete problems of ecological and evolutionary dynamics in structured graphs (60), and NP-hardness was stated for the quantitative populations (e.g., considered in 7, 8, 11, 28, 37, 42, 43, 50, 51, 57), problem (7). The review by Shakarian et al. (57) identifies the complexity of computing fixation probabilities on evolutionary and (ii) they significantly improve the complexity result of Lieber- graphs as an important open question in the area In that review, man et al. (7) and solve the computational complexity questions of two open problems (2.1 and 2.2) are identified that ask for the the area as identified in the review by Shakarian et al. (57). complexity of computing the exact fixation probabilities for graphs and for games on graphs. Our results not only present answers to Methodological Insight. Our proof ideas also reveal some important thaw crucial questions but also show that both the approximation points. We show how evolutionary processes in structured pop- problem and the qualitative question are computationally hard. The ulations can mimic aspects of computation. This insight could be most interesting aspects of our results are the lower bounds, which useful for future research on understanding the computational show that there exists no efficient algorithm in most cases, under the complexities of other stochastic processes on population structures. 1. Moran PAP (1958) Random processes in genetics. Proc Camb Philos Sac 59(1):60-71. 32. Szabo G, Antal T, Stab:. P, Droz M (2000) Spatial evolutionary prisoner's dilemma 2. Maruyama T (1970) Effective number of alleles In a subdivided population. Theo, game with three strategies and external constraints. Phys Rev E Stet Phys Names Papal Nol 1(31:273-306. fluids Rear Intesdisca Topics 62(1 Pt €1:1095-1103. 3. Slatkin M 09811Fixation probabilities and fixation tines in a subdivided population. 33. Kerr B. Riley MA. Feldman MW, Bohannon B/M (2002) local dispersal promotes EvohrtIOn 35131:477-898. blodiversity m a real-life game of rock-paper-scissors. Nature 418(6694):ln-174. 4. Wright S (1931) Evolution in Mendelian populations. Generics 16(21:97-159. 34. Hating D. Yu W (2008) Migration as a mechanism to promote cooperation. Adv 5. Mir 5 (1932) The roles of fatilatION inbreeding crosstreedng and selection in evo- Complex Syst 110):641-652. iution. PrOststatiVS of the Sixth International Congress oFGenetics Mach New Yerl). PP 35. TarnitaCE,Ohtsukift Antal T, fu F, Nowak MA (2009) Strategy selection in structured 356-M4 populations. 1 Meer Ri