triangle_detection (689B)
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 13 Up: [computational_problem] on [graph], [conjunctive_query], [fine_grained_complexity_problems] 14 15 See also: [all_edge_triangle], [boolean_matrix_multiplication], [sparse_triangle]