In an undirected (and unweighted) graph, to find the shortest cycle containing a specific vertex $s$, it is usually said to run a BFS from $s$ and the first time to find a re-visit, then that is the wanted smallest cycle length.

This does not seem to be true, quoting from https://www.cs.princeton.edu/courses/archive/spr08/cos226/exams/fin-f05-sol.pdf page 3:

Note that if you run BFS from $s$ and stop as soon as you revisit a vertex (using a previously ununused edge), you may not get the shortest path containing $s$.

Examples where this technique seems to be suggested: An efficient algorithm to find a shortest cycle including a specific vertex

Another technique, finding the shortest cycle in the whole graph, by running BFS from each vertex, also seems to detect only the shortestLength + 1 in a special case, as mentioned in this paper: https://link.springer.com/chapter/10.1007/978-3-540-78773-0_63 in the "Unweighted case". On the contrary, here (http://theory.stanford.edu/~virgi/cs267/lecture3.pdf) it is mentioned (first and second paragraphs) that running BFS from every vertex gives the shortest length (girth) in all cases. This is also mentioned in an archive (http://web.archive.org/web/20140513212046/https://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf).

Which of all algorithms/methods is true for:

  1. Finding the shortest-length cycle in an undirected graph?
  2. Finding the shortest-length cycle that passes through a known vertex $s$ in an undirected graph?
  3. Where is the pitfall in each of my above compare-and-contrasts? (I cannot believe that some of the above quoted might even be untrue...)

Note: A randomized sub-cubic algorithm seems to exist, in the paper "A shortest cycle for each vertex of a graph" by Raphael Yuster: http://research.haifa.ac.il/~raphy/papers/all-cycles.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy