Sink-free orientations: a local sampler with applications

For sink-free orientations in graphs of minimum degree at least 3, we show that there is a deterministic approximate counting algorithm that runs in time O((n73/varepsilon72)log(n/varepsilon)), a near-linear time sampling algorithm, and a randomised approximate counting algorithm that runs in time O((n/varepsilon)2log(n/varepsilon)), where n denotes the number of vertices of the input graph and 0<varepsilon<1 is the desired accuracy. All three algorithms are based on a local implementation of the sink popping method (Cohn, Pemantle, and Propp, 2002) under the partial rejection sampling framework (Guo, Jerrum, and Liu, 2019).