Document Open Access Logo

Triangle Estimation Using Tripartite Independent Set Queries

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.19.pdf
  • Filesize: 0.65 MB
  • 17 pages

Document Identifiers

Author Details

Anup Bhattacharya
  • Indian Statistical Institute, Kolkata, India
Arijit Bishnu
  • Indian Statistical Institute, Kolkata, India
Arijit Ghosh
  • Indian Statistical Institute, Kolkata, India
Gopinath Mishra
  • Indian Statistical Institute, Kolkata, India

Cite AsGet BibTex

Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Triangle Estimation Using Tripartite Independent Set Queries. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.19

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

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Triangle estimation
  • query complexity
  • sublinear algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nesreen K Ahmed, Nick Duffield, Jennifer Neville, and Ramana Kompella. Graph sample and hold: A framework for big-graph analytics. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1446-1455. ACM, 2014. Google Scholar
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems, pages 5-14. ACM, 2012. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  4. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  5. Ziv Bar-Yossef, Ravi Kumar, and D Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 623-632. Society for Industrial and Applied Mathematics, 2002. Google Scholar
  6. Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge Estimation with Independent Set Oracles. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pages 38:1-38:21, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.38.
  7. Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Triangle Estimation using Tripartite Independent Set Queries. CoRR, abs/1808.00691, 2018. URL: http://arxiv.org/abs/1808.00691.
  8. Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Hyperedge Estimation using Polylogarithmic Subset Queries. arXiv preprint, 2019. URL: http://arxiv.org/abs/1908.04196.
  9. Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh. Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers. In 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, pages 25:1-25:12, 2018. Google Scholar
  10. Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. Listing triangles. In International Colloquium on Automata, Languages, and Programming, pages 223-234. Springer, 2014. Google Scholar
  11. Luciana S Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 253-262. ACM, 2006. Google Scholar
  12. Sung-Soon Choi and Jeong Han Kim. Optimal query complexity bounds for finding graphs. Artificial Intelligence, 174(9-10):551-569, 2010. Google Scholar
  13. Graham Cormode and Hossein Jowhari. A second look at counting triangles in graph streams (corrected). Theoretical Computer Science, 683:22-30, 2017. Google Scholar
  14. Holger Dell and John Lapinskas. Fine-grained reductions from approximate counting to decision. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 281-288. ACM, 2018. Google Scholar
  15. Holger Dell, John Lapinskas, and Kitty Meeks. Approximately counting and sampling small witnesses using a colourful decision oracle. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.04826.
  16. Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. Google Scholar
  17. Talya Eden, Amit Levi, Dana Ron, and C Seshadhri. Approximately counting triangles in sublinear time. SIAM Journal on Computing, 46(5):1603-1646, 2017. Google Scholar
  18. Talya Eden, Dana Ron, and C Seshadhri. On approximating the number of k-cliques in sublinear time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 722-734. ACM, 2018. Google Scholar
  19. Uriel Feige. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM Journal on Computing, 35(4):964-984, 2006. Google Scholar
  20. Oded Goldreich and Dana Ron. Approximating average parameters of graphs. Random Structures & Algorithms, 32(4):473-493, 2008. Google Scholar
  21. Mira Gonen, Dana Ron, and Yuval Shavitt. Counting stars and other small subgraphs in sublinear-time. SIAM Journal on Discrete Mathematics, 25(3):1365-1411, 2011. Google Scholar
  22. Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing, 7(4):413-423, 1978. Google Scholar
  23. Svante Janson. Large deviations for sums of partly dependent random variables. Random Structures & Algorithms, 24(3):234-248, 2004. Google Scholar
  24. Madhav Jha, Comandur Seshadhri, and Ali Pinar. A space efficient streaming algorithm for triangle counting using the birthday paradox. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 589-597. ACM, 2013. Google Scholar
  25. Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting triangles in graphs. In International Computing and Combinatorics Conference, pages 710-716. Springer, 2005. Google Scholar
  26. John Kallaugher and Eric Price. A hybrid sampling scheme for triangle counting. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1778-1797. Society for Industrial and Applied Mathematics, 2017. Google Scholar
  27. Daniel M Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting arbitrary subgraphs in data streams. In International Colloquium on Automata, Languages, and Programming, pages 598-609. Springer, 2012. Google Scholar
  28. A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and Sampling Triangles from a Graph Stream. PVLDB, 6(14):1870-1881, 2013. Google Scholar
  29. Dana Ron and Gilad Tsur. The power of an example: Hidden set size approximation using group queries and conditional sampling. ACM Transactions on Computation Theory (TOCT), 8(4):15, 2016. Google Scholar
  30. Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg. Computing Exact Minimum Cuts Without Knowing the Graph. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pages 39:1-39:16, 2018. Google Scholar
  31. Larry Stockmeyer. The complexity of approximate counting. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 118-126. ACM, 1983. Google Scholar
  32. Larry Stockmeyer. On approximation algorithms for# P. SIAM Journal on Computing, 14(4):849-861, 1985. Google Scholar
  33. Kanat Tangwongsan, Aduri Pavan, and Srikanta Tirthapura. Parallel triangle counting in massive streaming graphs. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pages 781-786. ACM, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact