  The history of gene families -- which are equivalent to event-labeled gene
trees -- can to some extent be reconstructed from empirically estimated
evolutionary event-relations containing pairs of orthologous, paralogous or
xenologous genes. The question then arises as whether inferred event-labeled
gene trees are "biologically feasible" which is the case if one can find a
species tree with which the gene tree can be reconciled in a time-consistent
way.
  In this contribution, we consider event-labeled gene trees that contain
speciation, duplication as well as horizontal gene transfer and we assume that
the species tree is unknown. We provide a cubic-time algorithm to decide
whether a "time-consistent" binary species for a given event-labeled gene tree
exists and, in the affirmative case, to construct the species tree within the
same time-complexity.
