Sampling Arborescences in Parallel

arXiv2012.09502MaRDI QIDQ6356325FDOQ6356325

Aaron Schild, Amin Saberi, Nathan Hu, Nima Anari

Publication date: 17 December 2020

Abstract: 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 [Tut48], and sampling can be reduced to counting [JVV86, JS96]. 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 [Csa75]. 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.

This page was built for publication: Sampling Arborescences in Parallel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356325)