The Input/Output Complexity of Triangle Enumeration

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(E-3/2) I/Os (Dementiev, PhD thesis 2006) and O (E-2/(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 (E-3/2/(root MB)) expected I/Os, which improves the previous bounds by a factor min(root E/M, root M). Our algorithm is cache-oblivious and also I/O optimal: We show that any algorithm enumer- ating t distinct triangles must always use Omega (t/root MB) I/Os, and there are graphs for which t = Omega (E-3/2). Finally, we give a deterministic cache-aware algorithm using O (E-3/2/( root MB)) I/Os assuming M >= E-epsilon for a constant( )epsilon > 0. Our results are based on a new color coding technique, which may be of independent interest.