2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Just thought I would share this reference: sciencedirect.com/science/article/pii/S0304020808730196 $\endgroup$ Commented Aug 21, 2020 at 8:47
  • $\begingroup$ For lengths other than 4, I believe there are some more recent papers with improvements. Hope that you have a nice day! $\endgroup$ Commented Aug 21, 2020 at 8:47
  • $\begingroup$ In particular, Yuster and Zwick has a paper called "Finding Even Cycles Even Faster" which can find even cycles or output that that they don't exist in time $O(v^2)$. $\endgroup$ Commented Jul 18, 2023 at 19:51

3 Answers 3

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I guess that's what I was looking for. Thank you! $\endgroup$
    – user15816
    Commented Jun 16, 2011 at 16:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – Vijayender
    Commented Mar 5, 2017 at 10:54
5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ @Barry, welcome to MO! $\endgroup$ Commented Jun 17, 2011 at 5:33
  • $\begingroup$ 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) $\endgroup$
    – Vijayender
    Commented Mar 5, 2017 at 10:55
4
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ btw, it seems to run in $O(n^2)$, as you can create at most $\binom n 2$ edges in $G'$. $\endgroup$ Commented Jun 16, 2011 at 16:20
  • $\begingroup$ +1 for "keep it warm" $\endgroup$ Commented Jun 16, 2011 at 17:25
  • $\begingroup$ This is brilliant. An edge $(u,v)$ in $G'$ means "there is some vertex $w \in G\setminus\{u, v\}$ at distance $1$ from both $u$ and $v$". $\endgroup$ Commented Nov 6, 2021 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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