---
_id: '5421'
abstract:
- lang: eng
text: '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.
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.'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Chatterjee K, Ibsen-Jensen R, Nowak M. The Complexity of Evolution on Graphs.
IST Austria; 2014. doi:10.15479/AT:IST-2014-190-v2-2
apa: Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2014). The complexity
of evolution on graphs. IST Austria. https://doi.org/10.15479/AT:IST-2014-190-v2-2
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. The Complexity
of Evolution on Graphs. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-190-v2-2.
ieee: K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, The complexity of evolution
on graphs. IST Austria, 2014.
ista: Chatterjee K, Ibsen-Jensen R, Nowak M. 2014. The complexity of evolution on
graphs, IST Austria, 27p.
mla: Chatterjee, Krishnendu, et al. The Complexity of Evolution on Graphs.
IST Austria, 2014, doi:10.15479/AT:IST-2014-190-v2-2.
short: K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolution on
Graphs, IST Austria, 2014.
date_created: 2018-12-12T11:39:14Z
date_published: 2014-04-18T00:00:00Z
date_updated: 2023-02-23T12:26:33Z
day: '18'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-190-v2-2
file:
- access_level: open_access
checksum: 42f3d8b563286eb0d903832bd9a848d3
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:16Z
date_updated: 2020-07-14T12:46:50Z
file_id: '5538'
file_name: IST-2014-190-v2+2_main_full.pdf
file_size: 443529
relation: main_file
- access_level: open_access
checksum: 0c9a2fd822309719634495a35957e34d
content_type: application/pdf
creator: kschuh
date_created: 2019-09-06T07:30:20Z
date_updated: 2020-07-14T12:46:50Z
file_id: '6852'
file_name: IST-2014-190-v1+1_main_full.pdf
file_size: 440911
relation: main_file
file_date_updated: 2020-07-14T12:46:50Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '27'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '190'
related_material:
record:
- id: '5432'
relation: later_version
status: public
- id: '5440'
relation: later_version
status: public
status: public
title: The complexity of evolution on graphs
type: technical_report
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2014'
...