Listing Triangles
(2014) International Colloquium, ICALP 2014 In Automata, Languages, and Programming (Lecture notes in computer science) 8572. p.223234 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:
http://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
 in
 Automata, Languages, and Programming (Lecture notes in computer science)
 editor
 Esparza, Javier; Fraigniaud, Pierre; Husfeldt, Thore; Koutsoupias, Elias; ; ; and
 volume
 8572
 pages
 12 pages
 publisher
 Springer
 conference name
 International Colloquium, ICALP 2014
 external identifiers

 wos:000352643300021
 scopus:84904188201
 ISSN
 03029743
 16113349
 ISBN
 9783662439487
 DOI
 10.1007/9783662439487_19
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 a03045ea61e64d67b40321435077caf9 (old id 4813255)
 date added to LUP
 20141125 14:49:25
 date last changed
 20171001 03:14:32
@inproceedings{a03045ea61e64d67b40321435077caf9, 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 = {9783662439487}, issn = {03029743}, language = {eng}, pages = {223234}, publisher = {Springer}, title = {Listing Triangles}, url = {http://dx.doi.org/10.1007/9783662439487_19}, volume = {8572}, year = {2014}, }