# The Input/Output Complexity of Triangle Enumeration

arXiv: https://arxiv.org/abs/1312.0723 · HTML: https://mlsanity.com/paper/1312.0723/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2013.

## Built on by (most cited first, 1 of 1)

- [The I/O Complexity of Attention, or How Optimal is Flash Attention?](https://mlsanity.com/paper/2402.07443/) (2024)

## Abstract (arXiv)

We consider the well-known problem of enumerating all triangles of an undirected graph. Our focus is on determining the input/output (I/O) complexity of this problem. Let E be the number of edges, M<E the size of internal memory, and B the block size. The best results obtained previously are sort(E3/2) I/Os (Dementiev, PhD thesis 2006) and O(E2/(MB)) I/Os (Hu et al., SIGMOD 2013), where sort(n) denotes the number of I/Os for sorting n items. We improve the I/O complexity to O(E3/2/(√M B)) expected I/Os, which improves the previous bounds by a factor min(√E/M,√M). Our algorithm is cache-oblivious and also I/O optimal: We show that any algorithm enumerating t distinct triangles must always use Omega(t/(√M B)) I/Os, and there are graphs for which t=Omega(E3/2). Finally, we give a deterministic cache-aware algorithm using O(E3/2/(√M B)) I/Os assuming M≥ E^varepsilon for a constant varepsilon > 0. Our results are based on a new color coding technique, which may be of independent interest.