Cycle of Length 4 in an Undirected Graph – Detection Algorithms

algorithmscyclesgraph theory

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.

Best Answer

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

Related Solutions

[Math] Finding all paths on undirected graph

Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)

The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.

Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.

Push s on the path stack and call search(s):

path // is a stack (initially empty)
seen // is a set

def stuck(x)
   if x == t
     return False
   for each neighbor y of x
     if y not in seen
       insert y in seen
       if !stuck(y)
         return False
   return True

def search(x)
  if x == t
    print path
    return
  seen = set(path)
  if stuck(x)
    return
  for each neighbor y of x
    if y not in path:
      push y on the path
      search(y)
      pop y from the path

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

[Math] Detecting Negative Cycles in Undirected Graphs

Unfortunately, the answer is negative in the general case!

Counterexamples can be easily constructed in the following way:

take a graph, that resembles a tree with at least one sufficiently long shortest path.
assign to each tree-edge weight $1$, and $-k\ < -2$ to two edges $e$ and $f$, which are at least $2k-2$ edges of weight $1$ apart.
insert two edges, that are not tree edges and resemble a perfect matching on the vertices adjacent to the two negative edges and assign weight $2$ to both edges.

With the above construction, we have created a negative cycle of length $-2k-2+4\ < -2$ that contains two non-tree edges.
The shortest cycle containing only a single non-tree edge and both negative edges is however $\ > (-2k)\ +\ (2k-2)\ +\ (2) \ge\ 0$.

This demonstrates that negative cycles may go undetected with the $MST$-heuristic; it may however still be useful as a fast sufficient check for negative cycles.

Best Answer

Related Solutions

[Math] Finding all paths on undirected graph

[Math] Detecting Negative Cycles in Undirected Graphs

Related Question