Biswas, Amartya Shankha ;
Eden, Talya ;
Rubinfeld, Ronitt
Towards a DecompositionOptimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
Abstract
We consider the problem of sampling and approximately counting an arbitrary given motif H in a graph G, where access to G is given via queries: degree, neighbor, and pair, as well as uniform edge sample queries. Previous algorithms for these tasks were based on a decomposition of H into a collection of odd cycles and stars, denoted D^*(H) = {O_{k₁},...,O_{k_q}, S_{p₁},...,S_{p_𝓁}}. These algorithms were shown to be optimal for the case where H is a clique or an oddlength cycle, but no other lower bounds were known.
We present a new algorithm for sampling arbitrary motifs which, up to poly(log n) factors, is always at least as good, and for most graphs G is strictly better. The main ingredient leading to this improvement is an improved uniform algorithm for sampling stars, which might be of independent interest, as it allows to sample vertices according to the pth moment of the degree distribution.
Finally, we prove that this algorithm is decompositionoptimal for decompositions that contain at least one odd cycle. These are the first lower bounds for motifs H with a nontrivial decomposition, i.e., motifs that have more than a single component in their decomposition.
BibTeX  Entry
@InProceedings{biswas_et_al:LIPIcs.APPROX/RANDOM.2021.55,
author = {Biswas, Amartya Shankha and Eden, Talya and Rubinfeld, Ronitt},
title = {{Towards a DecompositionOptimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {55:155:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14748},
URN = {urn:nbn:de:0030drops147480},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.55},
annote = {Keywords: Sublinear time algorithms, Graph algorithms, Sampling subgraphs, Approximate counting}
}
15.09.2021
Keywords: 

Sublinear time algorithms, Graph algorithms, Sampling subgraphs, Approximate counting 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Issue date: 

2021 
Date of publication: 

15.09.2021 