Advanced

Listing Triangles

Björklund, Andreas LU ; Pagh, Rasmus; Vassilevska Williams, Virginia and Zwick, Uri (2014) International Colloquium, ICALP 2014 In Automata, Languages, and Programming (Lecture notes in computer science) 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:
author
organization
publishing date
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
0302-9743
1611-3349
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
2014-11-25 14:49:25
date last changed
2017-10-01 03:14:32
@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 ω &lt; 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         = {0302-9743},
  language     = {eng},
  pages        = {223--234},
  publisher    = {Springer},
  title        = {Listing Triangles},
  url          = {http://dx.doi.org/10.1007/978-3-662-43948-7_19},
  volume       = {8572},
  year         = {2014},
}