We consider the problem of approximating the arboricity of a graph G = (V, E), which we denote by arb(G), in sublinear time, where the arboricity of a graph is the minimal number of forests required to cover its edge set. An algorithm for this problem may perform degree and neighbor queries, and is allowed a small error probability. We design an algorithm that outputs an estimate , such that with probability 1–1/poly(n), arb(G) ≤ ≤ clog2 n-arb(G), where n = |V| and c is a constant. The expected query complexity and running time of the algorithm are O(n/arb(G)) · poly(log n), and this upper bound also holds with high probability. This bound is optimal for such an approximation up to a poly (log n) factor. For the closely related problem of finding the densest subgraph, Bhattacharya et al. (STOC, 2015) showed that there exists a factor-2 approximation algorithm that runs in time O(n) · poly (log n). In a follow up work, McGregor et al. (MFCS, 2015) improved the approximation factor to (1 + ∊) with the same complexity.

We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise $ε$-close to the uniform distribution, in an \emph{amortized-efficient} fashion. We consider the adjacency list query model, where access to a graph $G$ is given via degree and neighbor queries. The problem of sampling a single edge in this model has been raised by Eden and Rosenbaum (SOSA 18). Let $n$ and $m$ denote the number of vertices and edges of $G$, respectively. Eden and Rosenbaum provided upper and lower bounds of $Θ^*(n/\sqrt m)$ for sampling a single edge in general graphs (where $O^*(\cdot)$ suppresses $\textrm{poly}(1/ε)$ and $\textrm{poly}(\log n)$ dependencies). We ask whether the query complexity lower bound for sampling a single edge can be circumvented when multiple samples are required. That is, can we get an improved amortized per-sample cost if we allow a preprocessing phase? We answer in the affirmative. We present an algorithm that, if one knows the number of required samples $q$ in advance, has an overall cost that is sublinear in $q$, namely, $O^*(\sqrt q \cdot(n/\sqrt m))$, which is strictly preferable to $O^*(q\cdot (n/\sqrt m))$ cost resulting from $q$ invocations of the algorithm by Eden and Rosenbaum. Subsequent to a preliminary version of this work, Tětek and Thorup (arXiv, preprint) proved that this bound is essentially optimal.