Skip to main content

# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### 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:
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
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
2021-10-06 03:04:59
```@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         = {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},
}

```