# Cycle of length 4 in an undirected graph

Can anyone give me a hint for an algorithm to find a simple cycle of length 4 (4 edges and 4 vertices that is) in an undirected graph, given as an adjacency list? It needs to use $O(v^3)$ operations (v is the number of vertices) and I'm pretty sure that it can be done with some kind of BFS or DFS.

The algorithm only has to show that there is such a cycle, not where it is.

Oh, and there is another way, with the BFS you mentioned. Iteratively, do a BFS from each node. By slightly modifying the BFS algorithm, you can instead of computing the distances from your source vertex to any other, remember the number of shortest paths from your source vertex to any other.

If there is a vertex at distance two which has at least 2 shortest paths to the source vertex, you have found your $C_4$. That's $O(n^3)$.

• I guess that's what I was looking for. Thank you! – user15816 Jun 16 '11 at 16:38
• A graph can have a cycle of length 4 and yet densely connected (shortest distance between any two nodes is 1). In such a scenario the algorithm above would yield nothing. – Vijayender Mar 5 '17 at 10:54

Let's assume your vertices are labeled from 1 to $n$ and your adjacency list has the form $(u_1,v_1), (u_2,v_2),..., (u_E,v_E)$, where $1 \le u_i < v_i \le n$ for $1 \le i \le E$. Note that $E$, the number of edges, is $O(n^2)$.

Start with a preprocessing step that converts the adjacency list to a list of neighbor sets $N_i$, one for each $i$ between 1 and $n$: For each $k$ from 1 to $E$, put $u_k$ in set $N_{v_k}$ and $v_k$ in set $N_{u_k}$. (Sorry, those sub-subscripts don't look right.) This takes $O(n^2)$ steps.

Now go through the list of pairs $i,j$ with $1 \le i < j \le n$. For each pair, find the intersection $N_i \cap N_j$, and count its size. If you find a pair $i,j$ for which $|N_i \cap N_j| > 1$, you've found your 4-cycle: vertices $i$ and $j$ are each joined to two other vertices. (Neither $i$ nor $j$ is in $N_i \cap N_j$, since $k \notin N_k$ for any $k$.) The computation for each pair can be done in $O(n)$ steps, and there are $O(n^2)$ pairs, so the total computation takes $O(n^3)$ steps.

(Let me elaborate on why the computation of $|N_i \cap N_j|$ is $O(n)$. At worst, you can convert each neighborhood set into a 0--1 vector of dimension $n$ and then take the dot product of the two vectors.)

It might be of interest to ask a follow-up: Given an adjacency list of $E$ edges for a graph on $n$ vertices, can you detect the presence of a 4-cycle in $O(nE)$ steps?

• @Barry, welcome to MO! – Gerry Myerson Jun 17 '11 at 5:33
• Elegant, but dot product is O(n). But I guess this problem is from DasGupta Algorithms, where in we are asked to assume the format to be matrix or adjacency list whichever is easier for evaluation. Looping in pairs is O(n^2) and each dot product is O(n). Hence O(n^2 x n) – Vijayender Mar 5 '17 at 10:55

Build a graph $G'$ on $|V(G)|$ elements, and keep it warm.

Then, for any vertex $v$ of your graph $G$, add to $G'$ an edge for all of the $\binom {|N_G(v)|} {2}$ pairs of vertices at distance 1 from v. If at some point, you try to create an edge that had been created before, you have found a $C_4$

• btw, it seems to run in $O(n^2)$, as you can create at most $\binom n 2$ edges in $G'$. – Nathann Cohen Jun 16 '11 at 16:20
• +1 for "keep it warm" – Hans-Peter Stricker Jun 16 '11 at 17:25