  We consider the problem of decomposing the edges of a directed graph into as
few paths as possible. There is a natural lower bound for the number of paths
needed in an edge decomposition of a directed graph $D$ in terms of its degree
sequence: this is given by the excess of $D$, which is the sum of $|d^+(v) -
d^-(v)|/2$ over all vertices $v$ of $D$ (here $d^+(v)$ and $d^-(v)$ are,
respectively, the out- and indegree of $v$).
  A conjecture due to Alspach, Mason and Pullman from 1976 states that this
bound is correct for tournaments of even order. The conjecture was recently
resolved for large tournaments. Here we investigate to what extent the
conjecture holds for directed graphs in general. In particular, we prove that
the conjecture holds with high probability for the random directed graph
$D_{n,p}$ for a large range of $p$ (thus proving that it holds for most
directed graphs). To be more precise, we define a deterministic class of
directed graphs for which we can show the conjecture holds, and later show that
the random digraph belongs to this class with high probability. Our techniques
involve absorption and flows.
