Sink-free orientations: a local sampler with applications

Abstract

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((n^{73}/{\epsilon }^{72})\log (n/\epsilon ))$, a near-linear time sampling algorithm, and a randomised approximate counting algorithm that runs in time $O((n/\epsilon {)}^2\log (n/\epsilon ))$, where $n$ denotes the number of vertices of the input graph and $0<\epsilon <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).

15 pages, 1 figure. v2: updated discussion