leht CrossMark

leht CrossMark Computational complexity of ecological and evolutionary spatial dynamics Rasmus Ibsen-lensen bi, Krishnendu Chatterjee b, 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 computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for which the fastest possible algorithm requires exponential time. Another criterion is the space requirement of the algorithm. There is a crucial distinction between algorithms that can find a solution, verify a solution, or list several distinct solutions in given time and space. The complexity hierarchy that is generated in this way is the foundation of theoretical computer science. Precise complexity results can be notoriously difficult. The famous question whether polynomial time equals nondetenninistic polynomial time 0.e., P = NP) is one of the hardest open problems in computer science and all of mathematics. Here, we consider simple processes of ecological and evolutionary spatial dynamics. The basic question is: What is the probability that a new invader (or a new mutant) will take over a resident population? We derive precise com- plexity results for a variety of scenarios. We therefore show that some fundamental questions In this area cannot be answered by simple equations (assuming that P Is not equal to NP). evolutionary games I fixation probability I complexity classes Evolution occursin populations of reproducing individuals. Mutation generates distinct types. Selection favors some types over others. The mathematical formalism of evolution de- scribes how populations change in their genetic (or phenotypic) composition over time. Deterministic models of evolution are based on differential equations. They assume infinitely large population size and ignore demographic and other stochasticity. The more precise descriptions of evolutionary dynamics, however, use sto- chastic processes, which take into account the intrinsic randomness of when and where individuals reproduce and how many of their offspring survive. They also describe populations of finite size. A well-known stochastic process of evolution was formulated by Moran in 1958 (1). In any one-time step, a random individual is chosen proportional to fitness for reproduction and a random individual is chosen for death. The offspring of the first indi- vidual is added to the population. The total population size re- mains constant and is given by N. The original process was formulated for constant fitness, which means the fitness value of individuals does not depend on the relative abundance of various types in the population; it is a fixed number. The crucial question is: What is the probability that a newly introduced mutant will generate a lineage that takes over the entire population? This quantity is called the fixation probability. For the original Moran process, there is a simple formula. If the resident has fitness 1 and the mutant has fitness r, then the fixation probability of the mutant is given by p= (1 — 1/r)/(1 — 1/rw). The Moran process assumes that the biological population is well mixed. The offspring of any one individual can replace any other individual. If there is a spatial or social population struc- ture, then such is not the case. The question arises as to which population structures affect the outcome of evolution, for example, www.poeS.0rg/Cgild0i/10.107344MS.15I B66112 by modifying the fixation probability. The classic studies of Maruyama (2) and Slatkin (3) showed that symmetrical pop- ulation structures, such as regular lattices, do not change the fixation probability compared with the well-mixed population. The effect of population structure on evolution is also at the heart of the famous Wright-Fisher debate (4-6). In 2005, evolutionary graph theory was introduced as a tool to study how generalized population structures affect evolutionary outcome (7), and it has been studied in many other works (8-12). The individuals occupy the vertices of the graph. The links (edges) determine who interacts with whom for receiving payoff and for reproduction. There can be a single graph for game dynamical in- teraction and evolutionary replacement, or the interaction and re- placement graphs can be distinct (13). Often, the graph is held constant during evolutionary updating, but it is also possible to study dynamically changing graphs (14-22). The original Moran process is recovered as a special case given by the complete graph. It turns out that all isothermal graphs. where all vertices have the same rate of updating (the same "temperature"), have the same fixation probability as the well-mixed population (7). All symmet- rical population structures lead to isothermal graphs, but the con- verse is not true. Many evolutionary contests, however, are not fought out with constant fitness. Instead, the fitness of individual types depends on the frequency (is, relative abundance) of types in the pop- 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 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 matrix are the same and this property holds for all rows. Evo- lutionary game theory has traditionally been investigated with Significance An important question in evolution is: how does population structure affect the outcome of the evolutionary process? The theory of evolution in structured population has provided an impressive range of results, but an understanding of the com- putational complexity of even simple questions was missing. We prove that some fundamental problems in ecology and evolution can be precisely characterized by well-established computational complexity classes. This implies that the problems cannot be answered by simple equations. For example, there cannot be simple formulas for the fixation probability of a mutant given frequency -dependent selection in a structured population. We also show that, for example, calculating the molecular clock of neutral evolution in structured populations admit efficient algorithmic solutions. Author contributions: LC. and MAN. designed research performedresearch, and wrote the paper. The author declare no conflict of interest. This article Is a PNAS Direct Submissica. 'To whom correspondence should be addressed. Email: ribseninst ac et This article contains supportin information online at v.ww.pnas.orgilcokuprsupplidoi:10. I073/tinat. 1511366f IZNIX5uPPlernentat PNAS Early Edition I 1 of 6 EFTA01139453 deterministic equations describing infinitely large populations (23-26) and, more recently, has moved to finite population size and stochastic processes (27-38). Evolutionary games have a long history of being studied on spatial lattices (28, 39-42) and, more recently, on graphs (7, 27, 43, 44). The crucial quantity that needs to be calculated to evaluate natural selection is the fixation probability, p, of a newly introduced mutant that arises at a random position on the graph. If p > 1/N, where N is the population size, then natural selection favors the fixation of the new mutant, because a neutral mutant would have a fixation probability of I/N. In a contest between two strategies, another question would be if the fixation probability of the first strategy exceeds the fixation probability of the second strategy. If such is the case, then the first strategy would be more abundant in mutation-selection equilibrium for low mutation rate. The crucial problem is of the following form: Given a graph and a payoff matrix, what are the fixation probabilities of an individual of a new type arising in a population of the other type? Spatial structure plays an important role in many cases. For example, spatial structure can affect the rate of neutral evolution (45), and there are results that describe which spatial structures do or do not affect the outcome of constant selection (46-48). Some population structures can be amplifiers or suppressors of constant selection (7, 49, 50), meaning that they modify the in- tensity of selective differences. Finally, for evolutionary games, spatial structure can favor evolution of cooperation (28, 51). The study of spatial dynamics also has a long tradition in ecology (52-56). Here, the typical setting is that different species compete for ecological niches. Many evolutionary models are formally equivalent to ecological ones, especially if we consider only selection and not mutation. Then we can interpret the dif- ferent types of evolutionary games as different species. Again, a crucial question is: What is the probability that a newly introduced species can get established or take over an ecological niche? This paper is structured as follows. First, we give an intuitive ac- count of the foundation of theoretical computer science. We de- scribe classes of problems that can be solved by algorithms in certain time and space constraints. Subsequently, we present two simple problems of evolutionary dynamics in spatial settings. The first problem is motivated by a very simple ecological dynamic: the sec- ond problem is the general setting of evolutionary games on graphs. In both (-Agog the basic question is to calculate the takeover prob- ability (or fixation probability) of a new type. That is. we introduce a new type in a random position in the population, and we ask what is the complexity of an algorithm that can characterize the probability that the new type takes over the population (becomes fixed). Un- expectedly, we are able to prove exact complexity, results (Table 1). The class PTIME (denoted as P) consists of problems whose solutions can be computed by an algorithm that uses polynomial time. Formally, an algorithm uses polynomial time if the running time of the algorithm grows as a polynomial function of the size of the input. In computer science, P represents the class of problems that can be solved efficiently. The class nondeterministic polynomial time (denoted as NP) consists of problems for which solutions exist that are of polynomial length. and given a candidate for a solution of polynomial length, whether the candidate is indeed a solution can be checked in polynomial time. Therefore, an NP algorithm can verify a solution in polynomial time. To proceed further, we need the notion of "reduction" between classes of problems. A reduction, from a given problem Pi to a Table 1. Complexity results for various models and computational questions Model Qualitative Quantitative Ecological scenario Linear fitness Exponential fitness NP-complete PSPACE-complete P N P-complete PSPACE-complete PSPACE-complete problem P2, is a translation such that a solution for P2 can provide a solution for Pi. More precisely, if there is a polynomial -time reduction from Pr to P2, then a polynomial -time algorithm for P2 implies a polynomial -time algorithm for Pi. A given problem is NP-hard if for every problem in NP, there is a polynomial reduction to the given problem. A problem is NP- complete if it is both NP-hard and there is an NP algorithm for the problem. For example, consider a Boolean formula over variables, and the question of whether there exists an assignment to the vari- ables such that the formula is true. A polynomial candidate so- lution is an assignment of truth values to variables, and given a candidate assignment, the formula can be evaluated in poly- nomial time. This question is the famous satisfiability (SAT) problem in computer science. The SAT problem is NP-complete. The class P is contained in NP, and a major long-standing open question in computer science is whether P = NP. A polynomial - time algorithm for an NP-complete (or an NP-hard) problem would imply that P = NP, resolving the long-standing open problem. 'Ile class sharp (# P) intuitively corresponds to counting the number of solutions. A problem is in # P if it counts the number of distinct solutions such that (i) every possible candidate for a solution is of polynomial length, and (ii) given a candidate for a solution, it can be checked in polynomial time whether the candi- date is a solution. For example, given a Boolean formula, the problem of whether there are at least k distinct satisfying assign- ments to the formula is a # P-problem. A given problem is # P-hard, if for every # P-problem, there is a polynomial -time re- duction to the given problem. A # P-complete problem is a problem that is both # P-hard and for which there is a # P-solution. For example, counting the number of solutions in SAT is # P-oomplete. The class NP is contained in # P because, given the enumer- ation of solutions for # P, it is easy to check if there exists at least one solution. Intuitively, an NP problem asks whether there is at least one solution, whereas # P is the counting version that asks if there are least k distinct solutions (and the special case of It =I gives NP). Again, a major open question is whether NP = # P. Note that a polynomial -time algorithm for a # P-complete problem would be an even bigger result, because it would imply both P = NP and P = # P. The class PSPACE consists of problems that can be solved with polynomial space. Note that a polynomial space algorithm can reuse space and can, in general, require exponential time. Every # P problem can be solved in PSPACE by simply enumerating each candidate for a solution and checking if it is a solution. Because we can reuse space to enumerate the candidates for solutions, the enumeration can be achieved in polynomial space. Moreover, every polynomial -time algorithm uses, at most, polynomial space. Hence, it follows that # P is contained in PSPACE. The notion of PSPACE-hardness and PSPACE-completeness is similar to the notion of NP-hardness and NP-completeness, but with respect to the problems in PSPACE. Again, a long-standing open question in computer science is whether #P = PSPACE, and a polynomial - time algorithm for a ['SPACE-complete (or ['SPACE-hard) problem would imply P = NP = # P = PSPACE. We have mentioned that the major questions about the equality of the complexity classes are open problems, but the widely be- lieved conjecture is that P is strictly contained in NP, NP is strictly contained in # P, and # P is strictly contained in PSPACE. In other words, it is widely believed that NP-complete problems 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 illustration of the complexity classes is shown in Fig. I. Results The first problem is motivated by ecological dynamics. There is an ecosystem occupied by resident species. The spatial structure of the ecosystem is given by a graph. An invading species is in- 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 Fig. I. Pictorial illustration of the complexity classes P, NP, a P, and PSPACE. The 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 above a threshold, it, then the invader in the focal vertex cannot 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 A B A la b\ B kc di' Ill The entries of the payoff matrix can be positive or negative (or 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 fecundity equals the payoff sum. If the payoff sum is negative, then the fecundity is 0. We refer to this translation as linear fitness. In any one time step, a random individual is chosen for reproduction proportional to its fecundity. The offspring, which is of the same type as the parent, is placed into an adjacent position on the graph (illustrations are provided in Figs. 3 and 4). 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 Qt: Probability >IR Q2: Appracimate probability? 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 edges of the interaction graph and the red edges are the edges of the re- production graph. The probability of introducing a mutant in a specific vertex is always 1 over the number of vertices. The computational questions of interest regarding the takeover probability are as follows: whether the probability is positive (qualitative question) and what is an approximation of the probability (quantitative question). fixation probability subject to a small error. We prove the following results. The qualitative question is NP-hard and in PSPACE. The quantitative question is # P-hard and in PSPACE. The results follow from SI Appendir, Theorems 4. 8, and 15. Note that the first problem can also be obtained as a special case of the second problem. In the payoff matrix (1), we can set, for example, a =-1, b =1,c =d = O. This "game- has the property o * Ibsen-lensen et al. PNAS Fatty Edition I 3 of 6 EFTA01139455 IA VA a a a Sg. 3. Illustration of reproduction with matrix a ( e ) . The residents (type A) are colored blue, and the mutant (type 8) afe adored red. The black edges are the edges of the interaction graph, and the red edges are the edges of the reproduction graph. In the first figure beside each vertex, the payoff of the vertex (which is the sun of the payoff of the interactions) is shown. Because the first figure shows the payoff computation, the interaction edges that are re- sponsible for the payoff calculation are boldfaced. In the second figure, the vertex labeled 3 is selected for reproduction. The reproduction edges from vertex 3 are bddfaced and each edge has the probability 1/2. Finally, the successor S is chosen for replacement (i.e. vertex 3 reproduces to vertex 5). that type B never reproduces and type A reproduces until half of its neighbors are also of type A. This parameter choice leads to the same qualitative behavior and the same complexity bounds as described in the first problem. A generalization of games on graphs is the setting where the interaction graph and the replacement graph are distinct (13). Thus, each individual interacts with all of its neighbors on the interaction graph to receive payoff. Subsequently, an individual is chosen for reproduction proportional to its fecundity. The off- spring is placed randomly among all neighbors of the focal indi- vidual on the replacement graph. In this case, both the qualitative and quantitative questions become PSPACE-complete (S1 Ap- pendix, Theorem 15). 4 of 6 I wwwonts.orgfcgildoi/10.1073/6nas.1511366112 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 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 quantitative question has the same complexity as the previous problem (SI Appendix, Theorems 16 and 17). 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 variable x). Given instances of the 3SAT problem, we construct itstances of the 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 next), one for each dause. By means of mg construction, a vertex in this sequence can reproduce, at most, three times, one of which must be the next vertex of the sequence, with the others corresponding to, at most, two literals of the clause (intuitively, these two literals represent the ones that are not set to true by a candidate-satisfying assignment). The last vertex of the sequence reproduces to a new sequence of vertices that corresponds to an assignment of truth values to the variables. Each vertex in this new sequence can reproduce twice, one to the next vertex of the sequence and other to a variable or its negation. The variables or the 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 a satisfying assignment then with positive probability, all vertices can become mutant, and conversely. if there is no satisfying assignment then the proba- bility that all vertices become mutants is O. Madness of the Quantitative Ecologkal Problem. A Y P-complete problem is counting the number of perfect matthings in a bipartite graph (which also 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 right side, with edges from the left side to the right side. A perfect matching is a one-to-one mapping of each vertex of the left side to a vertex on the right side such that there is an edge between them. First, we argue that for the hardness proof, it suffices to consider bipartite graphs in which each vertex on the left side has an out-degree of 2v for some integer k. A key idea in our construction is that in a full binary tree, if the root becomes a mutant Ibsen-Jensen et al. EFTA01139456 Peve now n4•111,. eq144.161 &lino and every vertex can reproduce exactly once, then the set of mutants will eventually consist of a path from the root to a leaf, chosen uniformly at 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 side of the bipartite graph to mutants. Each of the vertices on the left side is the root of a full binary tree, where the leaves correspond to the right side of the bipartite graph. We show that the fixation process corresponds to a perfect matching (defined from the path in the full binary trees), and given an approximation of the fixation probability, the exact number of perfect matchings of the bipartite graph can be computed. PSPACE-Hardness for the Game on Evolutionary Graph Problem. Our PSPACE- hardness proof shows that the evolutionary process can solve the following concurrent -if problem, which we show is PSPACE-hard. The concurrent -if problem consists of a set of Boolean variables xi,x2, ,x,,, with a given initial truth assignment to the variables, and a set of if-statements. Each if- statement s, is of the following form: If a conjunctive clause C, over the variables is true, then assign a truth value to a variable (e.g„ if (xinx.nis), then xi is assigned false). The problem is to decide whether the first variable (Which is the accepting variable) eventually becomes true. We show that each variable can be represented as four vertices, and each if-statement as a single vertex, in the evolutionary graph and the evolutionary process can mimic the execution of the concurrent -if problem. Finally, if the accepting variable becomes true, then it corresponds to making a special vertex in the evolutionary graph as a mutant. There exists a part of the evolutionary graph that can only become mutants after the special vertex has become a mutant. Using this construction, we show that both the qualitative and quantitative problems are PSPACE-hard for evolutionary games on graphs. Discussion In summary, we have established computational complexity results for some fundamental problems of ecological and evolutionary 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 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 dynamics in structured populations. Our main results are summa- rized in Table 1. We now discuss the significance of our findings. interdisdplinary Connection. Although both computer science and biology examine the proliferation of information in time and space, the deep connection between them has been largely unexplored. Our work provides precise computational complexity insults for several well-studied problems in biology and can be viewed as a step to establish a connection between the two disciplines. Well-Studied Open Problem. The problems we have considered are basic aspects of well-studied questions for ecological and evo- lutionary dynamics in structured populations (7, 28, 37, 42, 50, 51). Several reviews have been written on this topic (8, 11, 43, 57). We first discuss the significance of an algorithmic approach in evolutionary graph theory. An efficient algorithm, which con- siders all (even worst-case) graphs for evolutionary processes, is important for the following reasons. First, it has been shown that some population structures (called amplifiers) can increase the effect of natural selection (7,51), but amplifiers are rare and constructing them is difficult (7, 11, 50, 51, 58, 59). If there were an efficient algorithmic approach that worked for all graphs, then one could design candidates for amplifiers and efficiently check their fixation probabilities. Be- cause there exists no algorithmic approach, research has to focus on special classes of graphs to identify simple formulas, such as calculating the fixation probabilities on star-like graphs (58). Second, it is known that some population structures and evo- lutionary dynamics promote evolution of cooperation but that others do not (51). An important open problem is to characterize 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 no efficient algorithm exists, one has to study special cases, for example, by considering nearly regular graphs (51). Thus, a general algorithmic approach is a very important problem for the well-studied question concerning the effect of population structures on evolutionary dynamics. An algorithmic approach has been studied for important special cases, such as for complete graphs (60), and NP-hardness was stated for the quantitative problem (7). The review by Shakarian et al. (57) identifies the complexity of computing fixation probabilities on evolutionary graphs as an important open question in the area In that review, two open problems (2.1 and 2.2) are identified that ask for the complexity of computing the exact fixation probabilities for graphs and for games on graphs. Our results not only present answers to thaw crucial questions but also show that both the approximation problem and the qualitative question are computationally hard. The most interesting aspects of our results are the lower bounds, which show that there exists no efficient algorithm in most cases, under the 1. Moran PAP (1958) Random processes in genetics. Proc Camb Philos Sac 59(1):60-71. 2. Maruyama T (1970) Effective number of alleles In a subdivided population. Theo, Papal Nol 1(31:273-306. 3. Slatkin M 09811 Fixation probabilities and fixation tines in a subdivided population. EvohrtIOn 35131:477-898. 4. Wright S (1931) Evolution in Mendelian populations. Generics 16(21:97-159. 5. Mir 5 (1932) The roles of fatilatION inbreeding crosstreedng and selection in evo- iution. PrOststatiVS of the Sixth International Congress oFGenetics Mach New Yerl). PP 356-M4 6. Fisher RA (19501 The -Sewell Wright Effect'. Heredity (Edina) 4(1)117-119. 7. Ueberman E. Haven C. NOwak MA (2005) Evolutionary dynamo on graphs. Nature 931(7023):112-316. 8. Stab0 G. Rath G (2007) Evolutionary games on graphs. Phys Rep 446(4-6)17-216. 9. Yang It.X. Wu 2X. Du WB (2012) Evolutionary games on scale free networks with tunable degree distribution. Europhys tett 99(1):10806. 10. Own YT (2013) Sharp benefit-to-cost rules for the evolution of cooperation on reg- ular graphs. Ann App.( Nasals 23(2)617-664. Allen B. Nowak MA (2014) Games on graphs. European Mathematical Society Surveys in Mathematical Sciences 1(1):113-151. 12. Oebarre f, Hauert C, Doebeli M 0014) Social evolution in structured populations. Nat Common 5:3409. 13. Ohtsuki µ Pacheco lµ Nowak MA (2007) Evolutionary graph theory: Breaking the symmetry between interaction and replacement. f Theor Riot 246(4681-69a. 19. Skyrms B. Penland. R (2000) A dynamic model of social network formation. Not Natl Aced Sci USA 97(104340-9346. Is. Pacheco /M. Traulsen A. Nowak MA (2006) Coevolution of strategy and structure m complex networks with dynamical linking. Phys Rev Lett 97(25):258103. 16. fu F, Rouen C. Now* MA Wang L (2008) Reputation -based partner choice promotes cooperation In sooal new.orks My, kW E Stet Months Soft Matter Phys 78(2 Pt 2) 026117. 17. Antal T, Ohtsuicilt Wakeley s. Taylor PO, Nowak MA (2009) Evolution of cooperation by Phenotypic similarity. Not Nati Aced SO USA 106(21):8597-8600. It Tamita CE, Antal T, Ohtsuki µ Nowak MA (2009) Evolutionary dynamics In set structured populations. Proc Nati Arad Sc? USA 106(211:8601-8604. 19. Szolnoki A. Peet M (2009) Resolving social dilemmas on evolving random networks. EurophyS Lett 86(3)30007. 20. Cava€ere M, Sedwards S, Tamita CE. Nowak MA, Csiluisz.Nagy A (2012) Prosperity is associated with instability in dynamical networks.) , Meth: Skil 299(0):126-138. 21. Rand DG, Arbesman S, Christakis NA (2011) Dynamic social networks promote co- operation in experiments with humans. ProcNadArad Sri LISA 108(48):19193-19198. 22. Wu B. et al. (2010) E./OK:Hall of cooperation on stochastic dynamical networks. PLOS One S(6)e11187. 23. Smith /M (1982) Evolution and the Theory of Games (Cambridge Univ Press. Cambridge. UK). 24. Hoibauer 1, Sigmund K. Sr (1988) The Theory of Evolution and Dynamical Systems: Mathematkal Aspects of Selection (Cambridge Vniv Press. Cambridge. UK). 25. Hofbauer 1, Sigmund K (1998) Evolutionary Games and Population Dynamics (Cam- bridge Univ Press, Cambridge, UK). 26. CreSSman R (2003) Evolutionary Dynamics and Extensa.. Form GEM'S, Economic Learning and Social Evolution (MIT Press. Cambridge, MA). 27. Broom M. Rychter 1 0013) Game-theoretical models in biology. Chapman 6 HaNCRC Mathematkal and Computational Biology (Chapman P. mewcac. Boa Baton. FL). 28. Nowak MA May RM (1992) Evolutionary games and spatial chaos. Nature 359(6398) 826-829. 29. Eliseo G (1993) teaming. bed iMeraction, and coordna6on. Economehica 61(5k1047-1071. 30. Herz AV (1994) Collective phenomena in spatially extended evolutionary games. I 771e0r Blot 1690).65-87. 31. Nakamaru M, Nogami µ Nana Y (1998) Score-dependent fertility model for the evolution of cooperation In a lattice. $ Theo, &NJ 194(0:101-124. widely believed conjecture that P is different from NP. A simple equation-based solution would give an efficient algorithm; thus, our result formally shows that for evaluating the fixation probability in spatial settings there does not exist a simple equation-based solu- tion in general. Our results are significant for the following reasons: (1) They establish the computational complexity for fundamental problems of ecological and evolutionary dynamics in structured populations (e.g., considered in 7, 8, 11, 28, 37, 42, 43, 50, 51, 57), and (ii) they significantly improve the complexity result of Lieber- man et al. (7) and solve the computational complexity questions of the area as identified in the review by Shakarian et al. (57). Methodological Insight. Our proof ideas also reveal some important points. We show how evolutionary processes in structured pop- ulations can mimic aspects of computation. This insight could be useful for future research on understanding the computational complexities of other stochastic processes on population structures. 32. Szabo G, Antal T, Stab:. P, Droz M (2000) Spatial evolutionary prisoner's dilemma game with three strategies and external constraints. Phys Rev E Stet Phys Names fluids Rear Intesdisca Topics 62(1 Pt €1:1095-1 103. 33. Kerr B. Riley MA. Feldman MW, Bohannon B/M (2002) local dispersal promotes blodiversity m a real-life game of rock-paper-scissors. Nature 418(6694):ln-174. 34. Hating D. Yu W (2008) Migration as a mechanism to promote cooperation. Adv Complex Syst 110):641-652. 35. TarnitaCE,Ohtsukift Antal T, fu F, Nowak MA (2009) Strategy selection in structured populations. 1 Meer Riot 259(3):570-581. 36. Pert M 520fiCki A 17010) Cr:evolutionary €amesa Mill review. Biosystems 9903:109-125, 37. van Veelen PA, Garcia 1, Rand DG, Nowak MA (2012) Direct reciprocity in structured populations. Prot Nati Arad Sd USA 109(25):9929-9934. 38. Nowak MA Sasaki A Taylor C. Fudenberg D (2004) Emergence of cooperation and evolutionary stability in finite populations. Nature 428(69831646-650. 39. KIllingisadC T. DOeteli M (1996) Spatial evolutionary game theory: Hawks and doves revisited. PIO( Viol Sc? 263(1374):1135-1144. 40. Szabo G, Take C (1998) Evolutionary prisoner's dilemma game on a square lattice. Phys Rev E Star Phys Plasmas Hui& Rein Mterdiscip Topics S8(1):69-73. 41. Static) G. Hauert C (2002) Phase Venation, and volunteering in spatial pubic goods games. Phys Rev Lett 89(111:118101. 42. Hallett C. Doebell M (2004) Spatial structure often Inhibits the evolution of co- operation in the snowdrift game. Nature 426(6983).643-646. 43. Nowak MA Tamita CE, Antal T (2010) Evolutionary dynamics in structured pop- ulations. Philos Trans R Soc Lond a Riot Sc) 365(15371:19-30. 49. Allen B, Tamita CE (2012) MeasureS of success In a dass of evolutionary models with fixed population size and structure. I Math Blot 680-21:109-143. 45. Allen B, et al. (2015) The molecular dock of neutral evolution can be accelerated or slowed by asymmetric spatial structure. PLOS Comput Biel 11(2):01004108. 46. Adlarn B, Nowak MA (2014) Universality of fixation probabilities in randomly struc- tured populations. Sc? Rep 4:6692. 47. Martryarna T (1974) A Markov process of gene frequency change In a geographically structured population. Genetics 76(21:367-377. 401. Barton NH (1993) The probability of fixation of a favoured allele in a subdivided population. Genet Res 62(21:149-157. 49. Nowak MA Who, F. lwase Y (2003) The linear process of somatic evolution. Pr* Ned Aced Sci LISA 100(25):14966-14969. 50. NOwak MA (2006) erolutionary Dynamics (Harvard Unit/Press. Cambridge. MA). 51. Ohtsuki µ Hauert C. Lieberman E. Nowak MA (2006) A simple rule for the evolution of cooperation on graphs and social networks. Nature 441(7092):502-505. 52. Durrett R. Levin S (1994) The importance of being discrete (and spatial). Meer Popo' Blot 4601:363-394. 53. Levin SA Paine RT (1974) Disturbance, patch formation, and community stnxtwe. Pros Nad Aad Sci USA 71(7)2744-2747. 54. Hassell MP, [mins MN, May RM (1904)kPaCies coexistence and self-organizing spatial dynamics. Nature 370(6487):290-292. 55. Tilman D, Karelva PM (1997) Spatial Ecology. The Role of Space in Population DYnamks and Mterspecilk Interactions (PIntetta INN Press. Princeton). 56. Dieckmann U, Law R, Metz NU, eds (2000) The Geometry of Ecological Interactions (Cambridge Univ Press, Cambridge, UK). Si. Shakarian P, Roos P, Johnson A (2012) A review of evolutionary graph theory with applications to game theory. Biosystems 107(2):66-80. 58. 441am B, Chatterlee K. Nowak is (2015) Amplifiers of selection. Prot R Sot Load A Math Phys Sat 4710181):201501 14. 59. Diaz 1, et aL (2013) On the fixation probability of superstars. Roc R Soc Land A Math Phys Sci469(21S6)tt0130191. 60. Diaz a at al. 0014) Approximating Nation probabilities in the generalized Moran process. Algodrivnica 690X78-kk 60f 6 I www.pnes.orgfcgildoi/10.1073/06.44.1511366112 lbSen.lensen et al. EFTA01139458 Supplementary Information: The computational complexity of ecological and evolutionary spatial dynamics Rasmus Ibsen-Jensent Krishnendu Chatterjeet Martin A. Nowakt t IST Austria PED, Harvard University 1 Introduction and Organization In this supplementary information we will present the detailed proofs of the results mentioned in the main text. To present a uniform treatment of the results we will consider the following notations: I. We will always consider that there are two types of individuals that occupy the vertices of the graph, and call them as mutants and residents (they represent type A and type B individuals, respectively, as mentioned in the main article). 2. To model the ecological scenario, that the mutants has an advantage that once they occupy a position, then the residents cannot win it over, we will model it as the case that the residents do not reproduce (note that a residents reproducing to another vertex which is a resident does not change the scenario of the graph). Organization of the results. The supplementary information is organized as follows: I. We start with the formal definitions of the model and the computational questions in Section 2. We will consider two functions to change payoffs to fitness, namely, linear bounded fitness (where the fitness is linear function of the payoff, but at least 0), and the exponential fitness function. In the three following sections after Section 2 we present results about the linear bounded fitness model. 2. In Section 3 and Section 4, we consider linear bounded fitness and no resident reproduction (that models the ecological scenario with advantage for the mutants). We establish NP-completeness of the qualitative question in Section 3, and #P-completeness of the quantitative question in Section 4. 3. In Section 5 we consider linear bounded fitness with resident reproduction, and show that both the qualitative and quantitative questions are PSPACE-complete. 4. We consider the exponential fitness function in Section 6. We show that the quantitative question for no resident reproduction, and the qualitative question (even with resident reproduction) can be solved in polynomial time. We show that the quantitative problem with resident reproduction is PSPACE-complete. 5. Finally, in Section 7 we argue that evolutionary games on well-mixed population, and finding the rate of molec- ular clock problem can be solved in polynomial time. 2 Models of Evolution on Graphs In this section we present the basic definitions related to the different models of evolution on graphs and the basic computational questions. Evolutionary graphs. An evolutionary graph C = (V, El, ER) consists of a finite set V of vertices; a set Et C V x V of interaction edges; and a set Eft C V x V of replacement (or reproduction) edges [121. The sets El and ER consist EFTA01139459 of directed edges. and the graph Of = (V, El) is called the interaction graph, and OR = (V, ER) is called the replacement graph. The graph GI is responsible for determining the interaction of individuals in the graph (which affects the fitness or payoff), and the graph OR captures the underlying structure for reproduction and replacement of individuals in the graph. Given an edge (v, ti) we say a is a successor of v and v is a predecessor of a. Payoff of individuals. Each vertex of the graph will be occupied by one of two types of individuals, namely, the resident type and the mutant type. In evolutionary games, along with the evolutionary graph there is a payoff matrix, which is defined as follows: R R (a b M c d where the entries of the matrix are rational numbers and represent the payoff of an interaction, i.e., a (resp., b) is the payoff of a resident type interacting with another resident (resp., mutant) type, and c (resp., d) is the payoff of a mutant type interacting with a resident (resp.. mutant) type. Given two vertices, x and v. we denote by pay(x, y) the payoff of the type of vertex x versus the type of vertex y. Fitness of individuals. The fitness of an individual denotes the fecundity (or reproductive rate) and must be a non- negative number. Let El(v) = {u I (v, u) E Er} denote the set of interaction successors of v. We define two natural (but not equivalent) ways of defining the fitness of v, denoted as f(v), as follows: I. Linear bounded fitness. The linear bounded fitness is the average payoff of the interactions but at least 0, i.e., f(v) = max {EuEEt(v)PaY(u,u) IE 1(4 Note that since the fitness is non-negative it is bounded from below by 0. 2. Exponential fitness. The exponential fitness is an exponential function of the average payoff of the interactions, i.e., f (a) exp EuE PaY(u, u) IE,(v)I Note that the fitness function ensures that the fitness is always positive. We will use LBF to refer to the linear bounded fitness function and ExF to refer to the exponential fitness function. The evolutionary process. The evolutionary process we consider is the classical birth-death process on an evolution- ary graph defined as follows: I. Initially all vertices of the graph are of the resident type and a mutant type is introduced uniformly at random at one of the vertices of the graph. 2. Repeat the following step (referred to as a generation): In every generation, a vertex v is selected proportional to the fitness of the individual at the vertex to reproducer. A new born individual replaces one of the replacement successors of v, i.e., it replaces a vertex chosen uniformly at random from the set ER(v) = fts I (v,u) E ER}. Step 2 (or generations) is repeated until nothing can change (in particular, if all vertices have fitness 0 or have the same type, then nothing can change). Fixation probability. The most relevant question from an evolutionary perspective is the fixation probability which is the probability that the mutant takes over the population, i.e., eventually all vertices become the mutant type. Computational questions. Given an evolutionary graph, a payoff matrix, and the payoff to fitness function (linear bounded, or exponential) we consider the following questions: I. the qualitative decision question asks whether the fixation probability is positive; and If every vertex has fitness 0. then no venex is selected for reproduction. EFTA01139460 2. the quantitative approximation question, given e > 0, asks to compute an approximation of the fixation proba• bility within an additive error of e. In this work we will establish several complexity bounds for the problem, and our most interesting results are the lower bounds. Lower bounds establish computational hardness of a problem, and if the lower bounds can be established even in restricted cases, then it shows that even special cases of the general problem is computationally hard, and thus the lower bounds become even more significant (e.g., a single lower bound for a special case can be applied to all generalizations of the special case). Special cases. There are several special cases of interest that we will explore. I. Constant fitness with density constraints. A special case of the payoff matrix is the constant fitness (aka constant selection) matrix defined as follows: R Df R r r M k 1 1) i.e., the mutant types always have fitness I and the resident types fitness r, where r ≥ 01. Along with the evolutionary graph and the payoff matrix, we have two thresholds, namely, Oj and Om, for the resident type and the mutant type, respectively. Intuitively, the thresholds represent a density constraint, and if an individual is surrounded by a lot of individuals of the same type, then its reproductive strength decreases. The density con• straint is relevant in many applications of evolution (see books [2, page 4701 [13, page 3201, also see Remark I). Let the selected vertex for reproduction be v. Let Same(v) denote the number of vertices in El (v) that are of the same type as v. If v is a mutant typ