triangle_detection (993B)
1 # Triangle detection 2 3 https://en.wikipedia.org/wiki/Triangle-free_graph#Triangle_finding_problem 4 5 [Computational_problem] of finding a [triangle] in an [undirected_graph] 6 7 [computational_complexity]: 8 - For [dense_graphs], the best known [algorithm] is via [boolean_matrix_multiplication] and takes O(n^omega) for n vertices (and for an input of size Theta(n^2)) 9 - [itai1977finding] 10 - For [sparse_graphs], it is possible to do Otilde(m^{2omega/(omega+1)}) [alon1997finding] 11 - [triangle_detection_conjecture] 12 - For [combinatorial_algorithms], the best known bounds are [cubic] up to [polylogarithmic] factors, and any [truly_subcubic] algorithm would imply a [truly_subcubic] algorithm for [Boolean_matrix_multiplication] 13 - cf [williams2018subcubic] 14 - cf https://people.csail.mit.edu/virgi/6.890/lecture2.pdf 15 16 Up: [computational_problem] on [graph], [conjunctive_query], [fine_grained_complexity_problems] 17 18 See also: [all_edge_triangle], [boolean_matrix_multiplication], [sparse_triangle]