Listing Triangles
(2014) International Colloquium, ICALP 2014 8572. p.223-234- Abstract
- We present new algorithms for listing triangles in dense and sparse graphs. The running time of our algorithm for dense graphs is O~(n^ω+n^3(ω−1)/(5−ω)t^2(3−ω)/(5−ω)), and the running time of the algorithm for sparse graphs is O~(m^2ω/(ω+1)+m^3(ω−1)/(ω+1)t^(3−ω)/(ω+1)), where n is the number of vertices, m is the number of edges, t is the number of triangles to be listed, and ω < 2.373 is the exponent of fast matrix multiplication. With the current bound on ω, the running times of our algorithms are O~(n^2.373+n^1.568t^0.478) and O~(m^1.408+m^1.222t^0.186), respectively. We first obtain randomized algorithms with the desired running times and then derandomize them using sparse recovery techniques.
If ω = 2, the running times of... (More) - We present new algorithms for listing triangles in dense and sparse graphs. The running time of our algorithm for dense graphs is O~(n^ω+n^3(ω−1)/(5−ω)t^2(3−ω)/(5−ω)), and the running time of the algorithm for sparse graphs is O~(m^2ω/(ω+1)+m^3(ω−1)/(ω+1)t^(3−ω)/(ω+1)), where n is the number of vertices, m is the number of edges, t is the number of triangles to be listed, and ω < 2.373 is the exponent of fast matrix multiplication. With the current bound on ω, the running times of our algorithms are O~(n^2.373+n^1.568t^0.478) and O~(m^1.408+m^1.222t^0.186), respectively. We first obtain randomized algorithms with the desired running times and then derandomize them using sparse recovery techniques.
If ω = 2, the running times of the algorithms become O~(n^2+nt^2/3) and O~(m^4/3+mt^1/3), respectively. In particular, if ω = 2, our algorithm lists m triangles in O~(m4/3) time. Pǎtraşcu (STOC 2010) showed that Ω(m^(4/3 − o(1))) time is required for listing m triangles, unless there exist subquadratic algorithms for 3SUM. We show that unless one can solve quadratic equation systems over a finite field significantly faster than the brute force algorithm, our triangle listing runtime bounds are tight assuming ω = 2, also for graphs with more triangles. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/4813255
- author
- Björklund, Andreas LU ; Pagh, Rasmus ; Vassilevska Williams, Virginia and Zwick, Uri
- organization
- publishing date
- 2014
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Automata, Languages, and Programming (Lecture notes in computer science)
- editor
- Esparza, Javier ; Fraigniaud, Pierre ; Husfeldt, Thore and Koutsoupias, Elias
- volume
- 8572
- pages
- 12 pages
- publisher
- Springer
- conference name
- International Colloquium, ICALP 2014
- conference location
- Copenhagen, Denmark
- conference dates
- 2014-07-08 - 2014-07-11
- external identifiers
-
- wos:000352643300021
- scopus:84904188201
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 978-3-662-43948-7
- DOI
- 10.1007/978-3-662-43948-7_19
- project
- Exact algorithms
- language
- English
- LU publication?
- yes
- id
- a03045ea-61e6-4d67-b403-21435077caf9 (old id 4813255)
- date added to LUP
- 2016-04-01 10:24:54
- date last changed
- 2025-01-14 14:09:23
@inproceedings{a03045ea-61e6-4d67-b403-21435077caf9, abstract = {{We present new algorithms for listing triangles in dense and sparse graphs. The running time of our algorithm for dense graphs is O~(n^ω+n^3(ω−1)/(5−ω)t^2(3−ω)/(5−ω)), and the running time of the algorithm for sparse graphs is O~(m^2ω/(ω+1)+m^3(ω−1)/(ω+1)t^(3−ω)/(ω+1)), where n is the number of vertices, m is the number of edges, t is the number of triangles to be listed, and ω < 2.373 is the exponent of fast matrix multiplication. With the current bound on ω, the running times of our algorithms are O~(n^2.373+n^1.568t^0.478) and O~(m^1.408+m^1.222t^0.186), respectively. We first obtain randomized algorithms with the desired running times and then derandomize them using sparse recovery techniques.<br/><br> If ω = 2, the running times of the algorithms become O~(n^2+nt^2/3) and O~(m^4/3+mt^1/3), respectively. In particular, if ω = 2, our algorithm lists m triangles in O~(m4/3) time. Pǎtraşcu (STOC 2010) showed that Ω(m^(4/3 − o(1))) time is required for listing m triangles, unless there exist subquadratic algorithms for 3SUM. We show that unless one can solve quadratic equation systems over a finite field significantly faster than the brute force algorithm, our triangle listing runtime bounds are tight assuming ω = 2, also for graphs with more triangles.}}, author = {{Björklund, Andreas and Pagh, Rasmus and Vassilevska Williams, Virginia and Zwick, Uri}}, booktitle = {{Automata, Languages, and Programming (Lecture notes in computer science)}}, editor = {{Esparza, Javier and Fraigniaud, Pierre and Husfeldt, Thore and Koutsoupias, Elias}}, isbn = {{978-3-662-43948-7}}, issn = {{1611-3349}}, language = {{eng}}, pages = {{223--234}}, publisher = {{Springer}}, title = {{Listing Triangles}}, url = {{http://dx.doi.org/10.1007/978-3-662-43948-7_19}}, doi = {{10.1007/978-3-662-43948-7_19}}, volume = {{8572}}, year = {{2014}}, }