# Sink-free orientations: a local sampler with applications

arXiv: https://arxiv.org/abs/2502.05877 · HTML: https://mlsanity.com/paper/2502.05877/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2025.

## Built on by (most cited first, 1 of 1)

- [Learning mathsfAC0 under Locally Sampleable Graphical Models](https://mlsanity.com/paper/2607.08303/) (2026)

## Abstract (arXiv)

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).