Triangle Detection via Complement Vertex Covers: A Fast Certifier with an Exact Fallback

Source abstract

We present Aegypti, a 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 reads three uncovered vertices, certified as a triangle in $\mathcal{O}(1)$. We prove unconditional soundness for both variants. The fast variant is a quadratic-time, one-sided certificate procedure: in the dense regime it is complete exactly when the Hvala cover of $\overline{G}$ leaves at least three vertices uncovered, a condition the factor-$2$ bound guarantees only for graphs with$\omega(G) \ge \lceil(n+3)/2\rceil$; its failure to return a triangle is not, by itself, evidence of triangle-freeness. The safe variant adds a Chiba--Nishizeki fallback and is therefore unconditionally complete, with worst-case running time $\mathcal{O}(n + m^{3/2})$. We make no claim against any fine-grained lower bound. Empirically, across a deterministic benchmark---random and structured families, adversarial dense families with small clique number, and an exhaustive sweep of all graphs on at most seven vertices---all routines agreed with an exact oracle and the fast dense branch recorded no miss. A public reference implementation is provided in the aegypti Python package, which depends on hvala.