---
res:
  bibo_abstract:
  - '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 for payoff 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. The fitness (or the reproductive rate) is a non-negative
    number, and depends on the payoff. 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 as follows: First, we consider
    a special case of the general problem, where the residents do not reproduce. We
    show that the qualitative question is NP-complete, and the quantitative approximation
    question is #P-complete, and the hardness results hold even in the special case
    where the interaction and the replacement graphs coincide. Second, we show that
    in general both the qualitative and the quantitative approximation questions are
    PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds
    even when the fitness is always positive.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Rasmus
      foaf_name: Ibsen-Jensen, Rasmus
      foaf_surname: Ibsen-Jensen
      foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-4783-0389
  - foaf_Person:
      foaf_givenName: Martin
      foaf_name: Nowak, Martin
      foaf_surname: Nowak
  bibo_doi: 10.15479/AT:IST-2015-323-v2-2
  dct_date: 2015^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/2664-1690
  dct_language: eng
  dct_publisher: IST Austria@
  dct_title: The complexity of evolutionary games on graphs@
...