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(n7/3) time, or alternatively in O(m4/3) time. This may come as a surprise since it invalidates several conjectures in the literature. In particular, - the O(n7/3) runtime surpasses the long-standing fastest algorithm for triangle detection based on matrix multiplication running in O(n^ω) = O(n2.372) time, due to Itai and Rodeh (1978). - the O(m4/3) runtime surpasses the long-standing fastest algorithm for triangle detection in sparse graphs based on matrix multiplication running in O(m2ω/(ω+1))= O(m1.407) time due to Alon, Yuster, and Zwick (1997). - the O(n7/3) time algorithm for triangle detection leads to a O(n25/9 logn) 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(m4/3) runtime invalidates a conjecture of A.~Abboud and V. V. Williams (FOCS 2014) that any combinatorial algorithm for triangle detection requires m3/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 Ne{{s}}et{{r}}il 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).