  We study the problem of sampling a uniformly random directed rooted spanning
tree, also known as an arborescence, from a possibly weighted directed graph.
Classically, this problem has long been known to be polynomial-time solvable;
the exact number of arborescences can be computed by a determinant [Tut48], and
sampling can be reduced to counting [JVV86, JS96]. However, the classic
reduction from sampling to counting seems to be inherently sequential. This
raises the question of designing efficient parallel algorithms for sampling. We
show that sampling arborescences can be done in RNC.
  For several well-studied combinatorial structures, counting can be reduced to
the computation of a determinant, which is known to be in NC [Csa75]. These
include arborescences, planar graph perfect matchings, Eulerian tours in
digraphs, and determinantal point processes. However, not much is known about
efficient parallel sampling of these structures. Our work is a step towards
resolving this mystery.
