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^{33}/\varepsilon^{32})\log(n/\varepsilon))$, a near-linear time sampling algorithm, and a randomised approximate counting algorithm that runs in time $O((n/\varepsilon)^2\log(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).

Konrad Anand

Postdoctoral Research Associate

I am a postdoctoral researcher in the School of Informatics at the University of Edinburgh, hosted by Heng Guo. I work in probability, combinatorics, and algorithms, particularly in counting, sampling, and randomization.

Graham Freifeld

Ph.D. Student

I am a Ph.D. student in the School of Informatics at the University of Edinburgh, advised by Heng Guo. My research interests are algorithms and complexity for counting and sampling problems, including counting and reconfiguration of planar structures.

Heng Guo

Reader

I am a Reader in Algorithms and Complexity in the School of Informatics at the University of Edinburgh. My research studies algorithms from a complexity perspective, particularly computational counting and sampling.

Chunyang Wang

Postdoc

I am Chunyang Wang (王淳扬), currently a project researcher (postdoc) at the National Institute of Informatics (NII), hosted by Prof. Yuichi Yoshida. My research interests broadly lie in theoretical computer science, especially algorithms for counting and sampling and algorithmic stability.

Jiaheng Wang

Postdoc

I am a HIIT Postdoctoral Fellow at the University of Helsinki, hosted by Mikko Koivisto. My research is in theoretical computer science, with a focus on algorithms and complexity for approximate counting and related combinatorial structures.