2026-08-12T12:57:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13622 2024-03-06T10:52:28Z ddc:004 open_access

Sampling Arborescences in Parallel Anari, Nima Hu, Nathan Saberi, Amin Schild, Aaron parallel algorithms arborescences spanning trees random sampling We study the problem of sampling a uniformly random directed rooted spanning tree, also known as an arborescence, from a possibly weighted directed graph. Classically, this problem has long been known to be polynomial-time solvable; the exact number of arborescences can be computed by a determinant [Tutte, 1948], and sampling can be reduced to counting [Jerrum et al., 1986; Jerrum and Sinclair, 1996]. However, the classic reduction from sampling to counting seems to be inherently sequential. This raises the question of designing efficient parallel algorithms for sampling. We show that sampling arborescences can be done in RNC. For several well-studied combinatorial structures, counting can be reduced to the computation of a determinant, which is known to be in NC [Csanky, 1975]. These include arborescences, planar graph perfect matchings, Eulerian tours in digraphs, and determinantal point processes. However, not much is known about efficient parallel sampling of these structures. Our work is a step towards resolving this mystery. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nima Anari and Nathan Hu and Amin Saberi and Aaron Schild 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.83 urn:nbn:de:0030-drops-136225 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.83 eng https://creativecommons.org/licenses/by/3.0/legalcode