Triangle Estimation using Polylogarithmic Queries.
Anup Kumar Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra · arXiv (Cornell University) · 2018
Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide the first approximate triangle counting algorithm using only polylogarithmic queries. Our query oracle Tripartite Independent Set (TIS) takes three disjoint sets of vertices $A$, $B$ and $C$ as input, and answers whether there exists a triangle having one endpoint in each of these three sets. Our query model is inspired by the Bipartite Independent Set (BIS) query oracle of Beame et al. (ITCS, 2018). Their algorithm for edge estimation requires only polylogarithmic BIS queries, where a BIS query takes two disjoint sets $A$ and $B$ as input and answers whether there is an edge with endpoints in $A$ and $B$. We extend the algorithmic framework of Beame et al., with TIS replacing BIS, for triangle counting using ideas from color coding due to Alon et al. (J. ACM, 1995) and a concentration inequality for sums of random variables with bounded dependency due to Janson (Rand. Struct. Alg., 2004).