The Arboricity Captures the Complexity of Sampling Edges

Talya Eden, Dana Ron, Will Rosenbaum

In this paper, we revisit the problem of sampling edges in an unknown graph $G=(V,E)$ from a distribution that is (pointwise) almost uniform over $E$. We consider the case where…