Aegypti v0.4.3: Triangle Detection via Lookahead Clique-Constrained Union-Find and a Residual Matching Fallback

Source abstract

We present \textsc{Aegypti} v0.4.3, a \emph{hybrid heuristic} for detecting a single triangle in an undirected graph $G = (V,E)$ with $n = |V|$ vertices and $m = |E|$ edges. The algorithm has a fast Phase~1 based on a sparse clique-constrained Union-Find structure (\textsc{FastCliqueUF}). It first unions a maximal matching $M$, then streams over the remaining edges. A rejected non-matching edge is not deleted immediately: it is kept alive for a fixed lookahead batch of size $32$, allowing nearby residual edges to complete a triangle before the failed edge is hidden from future clique tests. Phase~1 also uses a bounded common-neighbour probe on promising residual edges. These changes preserve linear Phase~1 work, $\mathcal{O}(n+m)$, while increasing the probability of early detection on triangle-rich graphs. If Phase~1 fails, Phase~2 computes a greedy vertex cover $C$ of the residual graph $G'=(V,E\setminus M)$ and performs adjacency-intersection enumeration only from that cover, while intersections still use the original graph so triangles touching a matching edge remain visible. Thus the fallback is not the full Chiba--Nishizeki scan over all vertices: its cost is $\mathcal{O}(r+\Phi_C)$, where $r=m-|M|$ and $\Phi_C$ is the sum of smaller-side intersection costs over residual base edges scanned from $C$. Since $\Phi_C \leq \mathcal{O}(r^{3/2})$, the coarse worst-case upper bound is $T(G)=\mathcal{O}(n+m+(m-|M|)^{3/2})$, while the implementation-specific bound is $T(G)=\mathcal{O}(n+m+\Phi_C)$. The worst-case exponent is still inherited from the classical Chiba--Nishizeki fallback; \textsc{Aegypti} is not claimed as a new asymptotic upper bound. Its contribution is practical: early exits on dense triangle-rich graphs, explicit witness triples, and a residual matching-edge and vertex-cover saving in the fallback. We evaluate v0.4.3 on an expanded 31-instance DIMACS benchmark suite. The smart algorithm wins $14$ individual instances, including $7$ of $8$ deliberately triangle-rich adversarial instances, while sparse matrix multiplication remains fastest in total time because dense triangle-free bipartite graphs force the fallback.