We present new algorithms for listing triangles in dense and sparse graphs. The running time of our algorithm for dense graphs is O(n~ω + n~(3(ω-1)/(5-ω))t~(2(3-ω)/(5-ω))), and the running time of the algo- rithm for sparse graphs is O(m~(2ω/(ω+1)) + m~(3(ω-1)/(ω+1))t~((3-ω)/(ω+1)), where n is the number of vertices, m is the number of edges, t is the number of triangles to be listed, and ω ＜ 2.373 is the exponent of fast matrix multiplication. With the current bound on ω, the running times of our algorithms are O(n~(2.373) +n~(1.568) t~(0.478)) and O(m~(1.408) + m~(1.222) t~(0.186)), respectively. We first obtain randomized algorithms with the desired running times and then derandomize them using sparse recovery techniques. If ω = 2, the running times of the algorithms become O(n~2 + nt~(2/3)) and O(m~(4/3) + mt~(1/3)), respectively. In particular, if ω = 2, our algorithm lists m triangles in O(m~(4/3)) time. Patrascu (STOC 2010) showed that Ω(m~(4/3-o(1))) time is required for listing m triangles, unless there exist subquadratic algorithms for 3SUM. We show that unless one can solve quadratic equation systems over a finite field significantly faster than the brute force algorithm, our triangle listing runtime bounds are tight assuming ω = 2, also for graphs with more triangles.
展开▼
