Return to Revisions

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.