A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications

Abstract

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^{\omega })=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\omega /(\omega +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}\log n)$ time combinatorial algorithm for $n\times 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 Ne{š}et{ř}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 \textsc{Max-Cut} problem, surpassing an almost $20$ years old algorithm of R.~R.~Williams (2005).

The triangle detection algorithm may fail. The analysis of Case 2.1 (in Subsection 2.1) is invalid. Thanks to Zach Hunter for pointing this out