  THIS IS A CORRECTED VERSION INCLUDING AN APPENDED CORRIGENDUM.
  Best match graphs arise naturally as the first processing intermediate in
algorithms for orthology detection. Let $T$ be a phylogenetic (gene) tree $T$
and $\sigma$ an assignment of leaves of $T$ to species. The best match graph
$(G,\sigma)$ is a digraph that contains an arc from $x$ to $y$ if the genes $x$
and $y$ reside in different species and $y$ is one of possibly many
(evolutionary) closest relatives of $x$ compared to all other genes contained
in the species $\sigma(y)$. Here, we characterize best match graphs and show
that it can be decided in cubic time and quadratic space whether $(G,\sigma)$
derived from a tree in this manner. If the answer is affirmative, there is a
unique least resolved tree that explains $(G,\sigma)$, which can also be
constructed in cubic time.
