Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Listing Triangles

Björklund, Andreas LU ; Pagh, Rasmus ; Vassilevska Williams, Virginia and Zwick, Uri (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:
author
; ; and
organization
publishing date
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
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
2016-04-01 10:24:54
date last changed
2024-06-16 16:43:45
@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}},
  doi          = {{10.1007/978-3-662-43948-7_19}},
  volume       = {{8572}},
  year         = {{2014}},
}