Current browse context:
cs.DS
Change to browse by:
References & Citations
Computer Science > Data Structures and Algorithms
Title: A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications
(Submitted on 2 Mar 2024 (v1), last revised 5 Mar 2024 (this version, v2))
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{\v{s}}et{\v{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 \textsc{Max-Cut} problem, surpassing an almost $20$ years old algorithm of R.~R.~Williams (2005).
Submission history
From: Adrian Dumitrescu [view email][v1] Sat, 2 Mar 2024 04:01:26 GMT (23kb,D)
[v2] Tue, 5 Mar 2024 15:14:48 GMT (0kb,I)
Link back to: arXiv, form interface, contact.