A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications

We revisit the algorithmic problem of finding a triangle in a graph: We give a randomized combinatorial algorithm for triangle detection in a given n-vertex graph with m edges running in O (n^7/3) time, or alternatively in O (m^4/3) time. This may come as a surprise since it invalidates several conjectures in the literature. In particular, - the O (n^7/3) runtime surpasses the long-standing fastest algorithm for triangle detection based on matrix multiplication running in O (n^) = O (n^2. 372) time, due to Itai and Rodeh (1978). - the O (m^4/3) runtime surpasses the long-standing fastest algorithm for triangle detection in sparse graphs based on matrix multiplication running in O (m^2/ (+1) ) = O (m^1. 407) time due to Alon, Yuster, and Zwick (1997). - the O (n^7/3) time algorithm for triangle detection leads to a O (n^25/9 n) time combinatorial algorithm for n n Boolean matrix multiplication, by a reduction of V. V. Williams and R. ~R. ~Williams (2018). This invalidates a conjecture of A. ~Abboud and V. V. Williams (FOCS 2014). - the O (m^4/3) runtime invalidates a conjecture of A. ~Abboud and V. V. Williams (FOCS 2014) that any combinatorial algorithm for triangle detection requires m^3/2 -o (1) time. - as a direct application of the triangle detection algorithm, we obtain a faster exact algorithm for the k-clique problem, surpassing an almost 40 years old algorithm of Nesetril and Poljak (1985). This result strongly disproves the combinatorial k-clique conjecture. - as another direct application of the triangle detection algorithm, we obtain a faster exact algorithm for the Max-Cut problem, surpassing an almost 20 years old algorithm of R. ~R. ~Williams (2005).