Approximate Triangle Counting via Sampling and Fast Matrix Multiplication
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 849 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 |
Redaktører | Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff |
Antal sider | 20 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2022 |
Artikelnummer | 107 |
ISBN (Elektronisk) | 9783959772358 |
DOI | |
Status | Udgivet - 2022 |
Begivenhed | 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, Frankrig Varighed: 4 jul. 2022 → 8 jul. 2022 |
Konference
Konference | 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 |
---|---|
Land | Frankrig |
By | Paris |
Periode | 04/07/2022 → 08/07/2022 |
Sponsor | CNRS, Inria, Nomadic Lab, Université Paris Cité |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 229 |
ISSN | 1868-8969 |
Bibliografisk note
Funding Information:
Funding The author was supported by the VILLUM Foundation grant 16582 and by the Bakala Foundation.
Publisher Copyright:
© Jakub Tětek; licensed under Creative Commons License CC-BY 4.0
ID: 342672660