  Horizontal gene transfer is an important contributor to evolution. According
to Walter M.\ Fitch, two genes are xenologs if they are separated by at least
one HGT. More formally, the directed Fitch graph has a set of genes is its
vertices, and directed edges $(x,y)$ for all pairs of genes $x$ and $y$ for
which $y$ has been horizontally transferred at least once since it diverged
from the last common ancestor of $x$ and $y$. Subgraphs of Fitch graphs can be
inferred by comparative sequence analysis. In many cases, however, only partial
knowledge about the ``full'' Fitch graph can be obtained. Here, we characterize
Fitch-satisfiable graphs that can be extended to a biologically feasible
``full'' Fitch graph and derive a simple polynomial-time recognition algorithm.
We then proceed to showing that finding the Fitch graphs with total maximum
(confidence) edge-weights is an NP-hard problem.
