Eden, Talya ;
Ron, Dana ;
Rosenbaum, Will
Almost Optimal Bounds for SublinearTime Sampling of kCliques in Bounded Arboricity Graphs
Abstract
Counting and sampling small subgraphs are fundamental algorithmic tasks. Motivated by the need to handle massive datasets efficiently, recent theoretical work has examined the problems in the sublinear time regime. In this work, we consider the problem of sampling a kclique in a graph from an almost uniform distribution. Specifically the algorithm should output each kclique with probability (1±ε)/n_k, where n_k denotes the number of kcliques in the graph and ε is a given approximation parameter. To this end, the algorithm may perform degree, neighbor, and pair queries. We focus on the class of graphs with arboricity at most α, and prove that the query complexity of the problem is Θ^*(min{nα , max {(((nα)^(k/2))/n_k)^{1/(k1)}, (nα^(k1))/n_k}}), where n is the number of vertices in the graph, and Θ^*(⋅) suppresses dependencies on (log n/ε)^O(k).
Our upper bound is based on defining a special auxiliary graph H_k, such that sampling edges almost uniformly in H_k translates to sampling kcliques almost uniformly in the original graph G. We then build on a known edgesampling algorithm (Eden, Ron and Rosenbaum, ICALP19) to sample edges in H_k. The challenge is simulating queries to H_k while being given query access only to G. Our lower bound follows from a construction of a family of graphs with arboricity α such that in each graph there are n_k kcliques, where one of these cliques is "hidden" and hence hard to sample.
BibTeX  Entry
@InProceedings{eden_et_al:LIPIcs.ICALP.2022.56,
author = {Eden, Talya and Ron, Dana and Rosenbaum, Will},
title = {{Almost Optimal Bounds for SublinearTime Sampling of kCliques in Bounded Arboricity Graphs}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {56:156:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16397},
URN = {urn:nbn:de:0030drops163974},
doi = {10.4230/LIPIcs.ICALP.2022.56},
annote = {Keywords: sublinear time algorithms, graph algorithms, cliques, arboricity, uniform sampling}
}
28.06.2022
Keywords: 

sublinear time algorithms, graph algorithms, cliques, arboricity, uniform sampling 
Seminar: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Issue date: 

2022 
Date of publication: 

28.06.2022 