2026-08-17T08:33:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24426 2025-12-12T15:01:45Z ddc:004 open_access

Sink-Free Orientations: A Local Sampler with Applications Anand, Konrad Freifeld, Graham Guo, Heng Wang, Chunyang Wang, Jiaheng Sink-free orientations local sampling deterministic counting 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/ε^32)log(n/ε)), a near-linear time sampling algorithm, and a randomised approximate counting algorithm that runs in time O((n/ε)²log(n/ε)), where n denotes the number of vertices of the input graph and 0 < ε < 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konrad Anand and Graham Freifeld and Heng Guo and Chunyang Wang and Jiaheng Wang 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.60 urn:nbn:de:0030-drops-244267 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.60 eng https://creativecommons.org/licenses/by/4.0/legalcode