License:
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.52
URN: urn:nbn:de:0030-drops-106287
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10628/
Eden, Talya ;
Ron, Dana ;
Rosenbaum, Will
The Arboricity Captures the Complexity of Sampling Edges
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(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).
BibTeX - Entry
@InProceedings{eden_et_al:LIPIcs:2019:10628,
author = {Talya Eden and Dana Ron and Will Rosenbaum},
title = {{The Arboricity Captures the Complexity of Sampling Edges}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {52:1--52:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10628},
URN = {urn:nbn:de:0030-drops-106287},
doi = {10.4230/LIPIcs.ICALP.2019.52},
annote = {Keywords: sampling, graph algorithms, arboricity, sublinear-time algorithms}
}
Keywords: |
|
sampling, graph algorithms, arboricity, sublinear-time algorithms |
Collection: |
|
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |
Issue Date: |
|
2019 |
Date of publication: |
|
04.07.2019 |