# Item

ITEM ACTIONSEXPORT

Released

Paper

#### The Arboricity Captures the Complexity of Sampling Edges

##### Fulltext (public)

arXiv:1902.08086.pdf

(Preprint), 359KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Eden, T., Ron, D., & Rosenbaum, W. (2019). The Arboricity Captures the Complexity of Sampling Edges. Retrieved from http://arxiv.org/abs/1902.08086.

Cite as: http://hdl.handle.net/21.11116/0000-0003-0CD0-5

##### Abstract

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 there is some a priori upper bound on the arboriciy
of $G$. Given query access to a graph $G$ over $n$ vertices and of average
degree $d$ and arboricity at most $\alpha$, we design an algorithm that
performs $O\!\left(\frac{\alpha}{d} \cdot \frac{\log^3 n}{\varepsilon}\right)$
queries in expectation and returns an edge in the graph such that every edge $e
\in E$ is sampled with probability $(1 \pm \varepsilon)/m$. The algorithm
performs two types of queries: degree queries and neighbor queries. We show
that the upper bound is tight (up to poly-logarithmic factors and the
dependence in $\varepsilon$), as $\Omega\!\left(\frac{\alpha}{d} \right)$
queries are necessary for the easier task of sampling edges from any
distribution over $E$ that is close to uniform in total variational distance.
We also prove that even if $G$ is a tree (i.e., $\alpha = 1$ so that
$\frac{\alpha}{d}=\Theta(1)$), $\Omega\left(\frac{\log n}{\log\log n}\right)$
queries are necessary to sample an edge from any distribution that is pointwise
close to uniform, thus establishing that a $\mathrm{poly}(\log n)$ factor is
necessary for constant $\alpha$. Finally we show how our algorithm can be
applied to obtain a new result on approximately counting subgraphs, based on
the recent work of Assadi, Kapralov, and Khanna (ITCS, 2019).