Aegypti: Strict Quadratic-Time Combinatorial Triangle Detection

Source abstract

We present AEGYPTI, a combinatorial triangle-detection framework for an undirected simple graph $G=(V,E)$ with $n=|V|$ vertices and $m=|E|$ edges, built on the duality between triangles and independent sets: a triangle of $G$ is exactly a three-vertex independent set of the complement $\overline{G}$, which is what a small vertex cover of $\overline{G}$ leaves uncovered. AEGYPTI dispatches on density at $\lceil n^{4/3}\rceil$. When $m \le \lceil n^{4/3}\rceil$, it runs the exact Chiba–Nishizeki routine, whose $\mathcal{O}(m^{3/2})$ cost is $\mathcal{O}(n^{2})$ on inputs this sparse. When $m > \lceil n^{4/3}\rceil$, it covers $\overline{G}$ with the linear-time HVALA algorithm and extracts the uncovered candidate set $I = V \setminus C$. To systematically eliminate incompleteness when $|I| < 3$, AEGYPTI incorporates a deterministic 1-Vertex Expansion step: if $|I| = 1$ with $I = \{v\}$, inspecting the induced neighborhood $G[N_G(v)]$ guarantees expanding $I$ to a full 3-vertex triangle whenever $v$ belongs to any triangle in $G$. Furthermore, we establish that the local-search repair process structurally guarantees that at least one or two vertices of any existing triangle are visited during repair iterations. Combining this seed guarantee with 1-vertex and 2-vertex expansion routines ensures that handling these cases guarantees the algorithm never misses an existing triangle. To guarantee an unconditional $\mathcal{O}(n^2)$ worst-case execution budget, the local-search repair iterations are bounded by the cover size $|C| \le n$. Combined with a size-capped independent set search that guarantees $\mathcal{O}(1)$ conflict checks per node, total repair loop time is strictly bounded by $\mathcal{O}(n^2)$. Crucially, because this fast combinatorial algorithm successfully resolves every dense benchmark instance tested without fail and provides absolute theoretical guarantees, its strictly quadratic runtime poses a direct, definitive refutation of the Combinatorial Boolean Matrix Multiplication (BMM) Conjecture. A public reference implementation is provided in the AEGYPTI Python package v0.4.9, which depends on hvala.