@online{Eden_arXiv1902.08086,
TITLE = {The Arboricity Captures the Complexity of Sampling Edges},
AUTHOR = {Eden, Talya and Ron, Dana and Rosenbaum, Will},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1902.08086},
EPRINT = {1902.08086},
EPRINTTYPE = {arXiv},
YEAR = {2019},
ABSTRACT = {In this paper, we revisit the problem of sampling edges in an unknown graph<br>$G = (V, E)$ from a distribution that is (pointwise) almost uniform over $E$.<br>We consider the case where there is some a priori upper bound on the arboriciy<br>of $G$. Given query access to a graph $G$ over $n$ vertices and of average<br>degree $d$ and arboricity at most $\alpha$, we design an algorithm that<br>performs $O\!\left(\frac{\alpha}{d} \cdot \frac{\log^3 n}{\varepsilon}\right)$<br>queries in expectation and returns an edge in the graph such that every edge $e<br>\in E$ is sampled with probability $(1 \pm \varepsilon)/m$. The algorithm<br>performs two types of queries: degree queries and neighbor queries. We show<br>that the upper bound is tight (up to poly-logarithmic factors and the<br>dependence in $\varepsilon$), as $\Omega\!\left(\frac{\alpha}{d} \right)$<br>queries are necessary for the easier task of sampling edges from any<br>distribution over $E$ that is close to uniform in total variational distance.<br>We also prove that even if $G$ is a tree (i.e., $\alpha = 1$ so that<br>$\frac{\alpha}{d}=\Theta(1)$), $\Omega\left(\frac{\log n}{\log\log n}\right)$<br>queries are necessary to sample an edge from any distribution that is pointwise<br>close to uniform, thus establishing that a $\mathrm{poly}(\log n)$ factor is<br>necessary for constant $\alpha$. Finally we show how our algorithm can be<br>applied to obtain a new result on approximately counting subgraphs, based on<br>the recent work of Assadi, Kapralov, and Khanna (ITCS, 2019).<br>},
}