Approximate Triangle Counting via Sampling and Fast Matrix Multiplication
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. / Tětek, Jakub.
49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. ed. / Mikolaj Bojanczyk; Emanuela Merelli; David P. Woodruff. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. 107 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 229).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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 -
ID: 342672660