thesis published Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Rasmus Ibsen-Jensen author 3B699956-F248-11E8-B48F-1D18A9856A870000-0003-4783-0389 Martin Nowak author KrCh department Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution.The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time. https://research-explorer.ista.ac.at/download/5432/5519/IST-2015-323-v1+1_main.pdf application/pdfno IST Austria2015 eng 2664-169010.15479/AT:IST-2015-323-v1-1 29 https://research-explorer.ista.ac.at/record/5421 https://research-explorer.ista.ac.at/record/5440 Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2015). <i>The complexity of evolutionary games on graphs</i>. IST Austria. <a href="https://doi.org/10.15479/AT:IST-2015-323-v1-1">https://doi.org/10.15479/AT:IST-2015-323-v1-1</a> K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015. K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015. Chatterjee, Krishnendu, et al. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015, doi:<a href="https://doi.org/10.15479/AT:IST-2015-323-v1-1">10.15479/AT:IST-2015-323-v1-1</a>. Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 29p. Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria; 2015. doi:<a href="https://doi.org/10.15479/AT:IST-2015-323-v1-1">10.15479/AT:IST-2015-323-v1-1</a> Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015. <a href="https://doi.org/10.15479/AT:IST-2015-323-v1-1">https://doi.org/10.15479/AT:IST-2015-323-v1-1</a>. 54322018-12-12T11:39:18Z2023-02-23T12:26:33Z