2026-07-25T09:51:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14704 2024-03-06T10:54:41Z ddc:004 open_access

An Optimal Algorithm for Triangle Counting in the Stream Jayaram, Rajesh Kallaugher, John Triangle Counting Streaming Graph Algorithms Sampling Sketching We present a new algorithm for approximating the number of triangles in a graph G whose edges arrive as an arbitrary order stream. If m is the number of edges in G, T the number of triangles, Δ_E the maximum number of triangles which share a single edge, and Δ_V the maximum number of triangles which share a single vertex, then our algorithm requires space: Õ(m/T⋅(Δ_E + √{Δ_V})) Taken with the Ω((m Δ_E)/T) lower bound of Braverman, Ostrovsky, and Vilenchik (ICALP 2013), and the Ω((m √{Δ_V})/T) lower bound of Kallaugher and Price (SODA 2017), our algorithm is optimal up to log factors, resolving the complexity of a classic problem in graph streaming. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rajesh Jayaram and John Kallaugher 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.11 urn:nbn:de:0030-drops-147046 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.11 eng https://creativecommons.org/licenses/by/4.0/legalcode