# Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle.

This procedure gives us the algorithmic complexity of $O(n^3)$.

It is well known that if $A$ is the adjacency matrix of $G$ then the number of triangles in $G$ is $tr(A^3)/6.$

Since matrix multiplication can be computed in time $O(n^{2.37})$ it is natural to ask:

Is there any (known) faster method for computing the number of triangles of a graph?

-

Let me cite this paper from 2007 (Practical algorithms for triangle computations in very large (sparse (power-law)) graphs by Matthieu Latapy):

The fastest algorithm known for finding and counting triangles relies on fast matrix product and has an $\mathcal{O}(n^\omega)$ time complexity, where $\omega < 2.376$ is the fast matrix product exponent. This approach however leads to a $\theta(n^2)$ space complexity.

There are some improvements for sparse graphs or if you want to list the triangles shown in the document.

-
I was aware of this result but somehow I thought in the last 5 years someone came up with a better algorithm –  Jernej Mar 7 '12 at 12:10
I did not know you are looking for some very recent algorithms, if you are researching in that area you could try to write a mail Matthieu Latapy. –  Listing Mar 7 '12 at 13:58
@Jernej: So, is there a faster algorithm? –  Eric Towers Jun 29 '14 at 6:32
@EricTowers No. It even turns out that a faster triangle counting algorithm would result in a faster matrix multiplication algorithm! –  Jernej Jun 29 '14 at 10:09