Triangle Estimation using Polylogarithmic Queries

Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra

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).

picture_as_pdf flag

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment