Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time

DOI10.4230/LIPICS.APPROX/RANDOM.2021.55arXiv2107.06582OpenAlexW3202472937MaRDI QIDQ6090913FDOQ6090913

Authors: Amartya Shankha Biswas, Talya Eden, Ronitt Rubinfeld 

Publication date: 20 November 2023

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 $mathcal{D}^{\ast }(H)=O_{k_1},ldots,O_{k_q},S_{p_1},ldots,S_{p_{e}ll}$. These algorithms were shown to be optimal for the case where $H$ is a clique or an odd-length cycle, but no other lower bounds were known. We present a new algorithm for sampling and approximately counting arbitrary motifs which, up to $extrmpoly(logn)$ factors, is always at least as good as previous results, 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 $p$-th moment of the degree distribution. Finally, we prove that this algorithm is emph{decomposition-optimal} 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.

Full work available at URL: https://arxiv.org/abs/2107.06582

zbMATH Keywords

graph algorithmsapproximate countingsublinear time algorithmssampling subgraphs

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (1)

• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs

This page was built for publication: Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090913)