I'm looking for an algorithm which just counts the number of simple and distinct 4-cycles in an undirected graph labelled with integer keys. I don't need it to be optimal because I only have to use it as a term of comparison.
Thank you in advance.
EDIT: I realize I only have to count true 4-cycles, which can be seen as empty squares. In other words, the two opposite vertices of the cycle have not to be connected. I think this constraint would achieve a higher research interest.
In an undirected graph with $m$ edges there can be as many as $\Theta(m^2)$ simple 4-cycles, so that's a reasonable time bound to aim for. And it's easy enough to achieve: set up a data structure that can test adjacency in constant time (e.g. a hash table or array indexed by pairs of vertices) and then, for each pair of oriented edges $uv$ and $xy$ perform the following two tests:
Are $uv$ and $xy$ two opposite edges in a 4-cycle? That is, are $vx$ and $yu$ also edges?
Is this a duplicate of another 4-cycle that we might list at another point in the algorithm? One way to prevent this is to only allow pairs of edges for which $u$ has the minimum index among all four vertices and $v$ has an index smaller than the index of $y$.
If it passes both tests, output it.
Here is an $O(VE)$ algorithm. The number of 4-cycles is $$\frac{1}{2}\sum_{\lbrace v,w\rbrace} \binom{c(v,w)}{2},$$ where the sum is over the $\binom{V}{2}$ pairs of vertices and $c(v,w)$ is the number of common neighbours of $v$ and $w$. For particular $v,w$, $c(v,w)$ can be found by scanning the neighbour lists of the $v$ and $w$ once each. In total each neighbour list is scanned $O(V)$ times.
This is answered in great generality by Alon/Yuster/Zwick.
For a less sophisticated (but more practical) answer than my other answer: The trace of $A(G)^4$ counts the number of $4$-cycles. It counts every simple cycle eight times (once for each basepoint, and once for each direction). It counts every quadruply covered edge twice (once for each endpoint). It counts each four-cycle of the form $ABCBA$ four times. Now, since the number of edges is easy to compute, and the number of the last kind of four-cycles is just equal to $\sum d(v) (d(v) - 1),$ your number of four-cycles is not hard to back out (and the complexity is $O(V(G)^\omega),$ just like Alon, Yuster, Zwick!
