  Probabilistic distributions over spanning trees in directed graphs are a
fundamental model of dependency structure in natural language processing,
syntactic dependency trees. In NLP, dependency trees often have an additional
root constraint: only one edge may emanate from the root. However, no sampling
algorithm has been presented in the literature to account for this additional
constraint. In this paper, we adapt two spanning tree sampling algorithms to
faithfully sample dependency trees from a graph subject to the root constraint.
Wilson (1996)'s sampling algorithm has a running time of $\mathcal{O}(H)$ where
$H$ is the mean hitting time of the graph. Colbourn (1996)'s sampling algorithm
has a running time of $\mathcal{O}(N^3)$, which is often greater than the mean
hitting time of a directed graph. Additionally, we build upon Colbourn's
algorithm and present a novel extension that can sample $K$ trees without
replacement in $\mathcal{O}(K N^3 + K^2 N)$ time. To the best of our knowledge,
no algorithm has been given for sampling spanning trees without replacement
from a directed graph.

Computation and Language