Approximate Triangle Counting via Sampling and Fast Matrix Multiplication
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Final published version, 849 KB, PDF document
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.
Original language | English |
---|---|
Title of host publication | 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 |
Editors | Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff |
Number of pages | 20 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2022 |
Article number | 107 |
ISBN (Electronic) | 9783959772358 |
DOIs | |
Publication status | Published - 2022 |
Event | 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, France Duration: 4 Jul 2022 → 8 Jul 2022 |
Conference
Conference | 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 |
---|---|
Land | France |
By | Paris |
Periode | 04/07/2022 → 08/07/2022 |
Sponsor | CNRS, Inria, Nomadic Lab, Université Paris Cité |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 229 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© Jakub Tětek; licensed under Creative Commons License CC-BY 4.0
- Approximate triangle counting, Fast matrix multiplication, Sampling
Research areas
ID: 342672660