TY - GEN

T1 - Approximate Triangle Counting via Sampling and Fast Matrix Multiplication

AU - Tětek, Jakub

N1 - Publisher Copyright: © Jakub Tětek; licensed under Creative Commons License CC-BY 4.0

PY - 2022

Y1 - 2022

N2 - There is a simple (equation presented) time algorithm for 1±ϵ-approximate triangle counting where T is the number of triangles in the graph and n the number of vertices. At the same time, one may count triangles exactly using fast matrix multiplication in time Õ(nω). Is it possible to get a negative dependency on the number of triangles T while retaining the state-of-the-art nω dependency on n? We answer this question positively by providing an algorithm which runs in time (equation presented). This is optimal in the sense that as long as the exponent of T is independent of n, T, it cannot be improved while retaining the dependency on n. Our algorithm improves upon the state of the art when T ≫ 1 and T ≪ n. We also consider the problem of approximate triangle counting in sparse graphs, parameterized by the number of edges m. The best known algorithm runs in time (equation presented) [Eden et al., SIAM Journal on Computing, 2017]. An algorithm by Alon et al. [JACM, 1995] for exact triangle counting that runs in time (equation presented). We again get an algorithm whose complexity has a state-of-the-art dependency on m while having negative dependency on T. Specifically, our algorithm runs in time (equation presented). This is again optimal in the sense that no better constant exponent of T is possible without worsening the dependency on m. This algorithm improves upon the state of the art when T ≫ 1 and T ≪ √m. In both cases, algorithms with time complexity matching query complexity lower bounds were known on some range of parameters. While those algorithms have optimal query complexity for the whole range of T, the time complexity departs from the query complexity and is no longer optimal (as we show) for T ≪ n and T ≪ √m, respectively. We focus on the time complexity in this range of T. To the best of our knowledge, this is the first paper considering the discrepancy between query and time complexity in graph parameter estimation.

AB - There is a simple (equation presented) time algorithm for 1±ϵ-approximate triangle counting where T is the number of triangles in the graph and n the number of vertices. At the same time, one may count triangles exactly using fast matrix multiplication in time Õ(nω). Is it possible to get a negative dependency on the number of triangles T while retaining the state-of-the-art nω dependency on n? We answer this question positively by providing an algorithm which runs in time (equation presented). This is optimal in the sense that as long as the exponent of T is independent of n, T, it cannot be improved while retaining the dependency on n. Our algorithm improves upon the state of the art when T ≫ 1 and T ≪ n. We also consider the problem of approximate triangle counting in sparse graphs, parameterized by the number of edges m. The best known algorithm runs in time (equation presented) [Eden et al., SIAM Journal on Computing, 2017]. An algorithm by Alon et al. [JACM, 1995] for exact triangle counting that runs in time (equation presented). We again get an algorithm whose complexity has a state-of-the-art dependency on m while having negative dependency on T. Specifically, our algorithm runs in time (equation presented). This is again optimal in the sense that no better constant exponent of T is possible without worsening the dependency on m. This algorithm improves upon the state of the art when T ≫ 1 and T ≪ √m. In both cases, algorithms with time complexity matching query complexity lower bounds were known on some range of parameters. While those algorithms have optimal query complexity for the whole range of T, the time complexity departs from the query complexity and is no longer optimal (as we show) for T ≪ n and T ≪ √m, respectively. We focus on the time complexity in this range of T. To the best of our knowledge, this is the first paper considering the discrepancy between query and time complexity in graph parameter estimation.

KW - Approximate triangle counting

KW - Fast matrix multiplication

KW - Sampling

U2 - 10.4230/LIPIcs.ICALP.2022.107

DO - 10.4230/LIPIcs.ICALP.2022.107

M3 - Article in proceedings

AN - SCOPUS:85133490463

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022

A2 - Bojanczyk, Mikolaj

A2 - Merelli, Emanuela

A2 - Woodruff, David P.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022

Y2 - 4 July 2022 through 8 July 2022

ER -