2024/03/02 by Dumitrescu, Adrian
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2403.01085
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š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 Max-Cut problem, surpassing an almost 20 years old algorithm of R.~R.~Williams (2005).