License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.19
URN: urn:nbn:de:0030-drops-115156
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11515/
Go to the corresponding LIPIcs Volume Portal

Bhattacharya, Anup ; Bishnu, Arijit ; Ghosh, Arijit ; Mishra, Gopinath

Triangle Estimation Using Tripartite Independent Set Queries

pdf-format:
LIPIcs-ISAAC-2019-19.pdf (0.7 MB)

Abstract

Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an approximate triangle counting algorithm using only polylogarithmic queries when the number of triangles on any edge in the graph is polylogarithmically bounded. 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 generally belongs to the class of group queries (Ron and Tsur, ACM ToCT, 2016; Dell and Lapinskas, STOC 2018) and in particular is inspired by the Bipartite Independent Set (BIS) query oracle of Beame et al. (ITCS 2018). 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 (Janson, Rand. Struct. Alg., 2004).

BibTeX - Entry

@InProceedings{bhattacharya_et_al:LIPIcs:2019:11515,
  author =	{Anup Bhattacharya and Arijit Bishnu and Arijit Ghosh and Gopinath Mishra},
  title =	{{Triangle Estimation Using Tripartite Independent Set Queries}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11515},
  URN =		{urn:nbn:de:0030-drops-115156},
  doi =		{10.4230/LIPIcs.ISAAC.2019.19},
  annote =	{Keywords: Triangle estimation, query complexity, sublinear algorithm}
}

Keywords: Triangle estimation, query complexity, sublinear algorithm
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI