Generating a random sink-free orientation in quadratic time (Q5960785)

Summary: 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. \textit{R. Bubley} and \textit{M. Dyer} [in: Proc. 8th Ann. ACM-SIAM Symp. Discrete Algorithms, 248-257 (1997)] used Markov chain Monte Carlo to sample approximately from the uniform distribution on sink-free orientations in time \(O(m^3 \log (1 / \varepsilon))\), where \(m\) is the number of edges and \(\varepsilon\) the degree of approximation. \textit{M. Huber} [in: Proc. 13th Ann. ACM Symp. Theory Comput., 31-40 (1998)] used coupling from the past to obtain an exact sample in time \(O(m^4)\). 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.