Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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)$.

share|improve this answer
    
I guess that's what I was looking for. Thank you! –  user15816 Jun 16 '11 at 16:38

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?

share|improve this answer
    
@Barry, welcome to MO! –  Gerry Myerson Jun 17 '11 at 5:33

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$

share|improve this answer
    
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 Stricker Jun 16 '11 at 17:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.