Generating a Random Sink-free Orientation in Quadratic Time

A sink-free orientation of a finite undirected graph is a choice of orientation for each edge such that every vertex has out-degree at least 1. Bubley and Dyer (1997) use Markov Chain Monte Carlo to sample approximately from the uniform distribution on sink-free orientations in time O(m³ log (1 / ε)), where m is the number of edges and ε the degree of approximation. Huber (1998) uses coupling from the past to obtain an exact sample in time O(m⁴). We present a simple randomized algorithm inspired by Wilson's cycle popping method which obtains an exact sample in mean time at most $O(nm)$, where n is the number of vertices.