Fast Triangle Detection and Enumeration in Undirected Graphs: The Aegypti Algorithm

The triangle finding problem is a cornerstone of complex network analysis, serving as the primitive for computing clustering coefficients and transitivity. This paper presents \( \texttt{Aegypti} \), a practical algorithm for triangle detection and enumeration in undirected graphs. By combining a descending degree-ordered vertex-iterator with a hybrid strategy that adapts to graph density, \( \texttt{Aegypti} \) achieves a worst-case runtime of \( \mathcal{O}(m^{3/2}) \) for full enumeration, which matches the bound established by Chiba and Nishizeki for arboricity-based listing algorithms. For the detection variant (\( \texttt{first_triangle}=\text{True} \)), we prove that sorting by non-increasing degree enables early termination in \( \mathcal{O}(n\log n + d_{\max}^2) \) worst-case time when the maximum-degree vertex participates in a triangle, where the quadratic factor in \( d_{\max} \) reduces to \( \mathcal{O}(d_{\max}/C(v_{\max})) \) in expectation when the local clustering coefficient \( C(v_{\max}) > 0 \). Experiments on complement graphs of DIMACS maximum-clique benchmark instances confirm that detection terminates sub-millisecond on the majority of instances, while the matrix-multiplication baseline requires substantially more time on the same inputs.