2026-07-22T11:00:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10628 2024-03-06T10:46:19Z ddc:004 open_access

The Arboricity Captures the Complexity of Sampling Edges Eden, Talya Ron, Dana Rosenbaum, Will sampling graph algorithms arboricity sublinear-time algorithms 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(alpha/d * {log^3 n}/epsilon) queries in expectation and returns an edge in the graph such that every edge e in E is sampled with probability (1 +/- epsilon)/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 epsilon), as Omega(alpha/d) 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 alpha/d = Theta(1)), Omega({log n}/{loglog n}) queries are necessary to sample an edge from any distribution that is pointwise close to uniform, thus establishing that a 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Talya Eden and Dana Ron and Will Rosenbaum 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.52 urn:nbn:de:0030-drops-106287 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.52 eng https://creativecommons.org/licenses/by/3.0/legalcode