Find the shortest cycle that contains a particular vertex on an undirected (and unweighted) chart $ s $It is usually said that a BFS is running $ s $ and the first time to find another visit, this is the smallest cycle length you want.
This does not seem to be true, quoted from https://www.cs.princeton.edu/courses/archive/spr08/cos226/exams/fin-f05-sol.pdf page 3:
Keep this in mind when you run BFS from $ s $ and stop once you visit a again
You may not get the vertex (using a previously unused edge)
shortest path contains $ s $,
Examples where this technique seems to be suggested: An efficient algorithm to find a shortest cycle including a specific vertex
Another technique, in which the shortest cycle in the entire diagram is determined by executing BFS from each vertex, seems to recognize only the shortest length +1 in a special case, as mentioned in this document: https: // link. springer.com/chapter /10.1007/978-3-540-78773-0_63 in the "unweighted case". on the other handHere (http://theory.stanford.edu/~virgi/cs267/lecture3.pdf) it is mentioned (first and second paragraph) that executing BFS results in every case from each vertex the shortest length (circumference). 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 applies to:
- Can you find the cycle with the shortest length in an undirected diagram?
- Find the shortest length cycle that passes through a known vertex $ s $ in an undirected graph?
- Where is the trap in each of my comparisons and contrasts above? (I can't believe some of the above are even wrong …)
Note: A randomized sub-cubic algorithm appears to exist in Raphael Yuster's publication "A shortest cycle for each vertex of a graph": http://research.haifa.ac.il/~raphy/papers/all-cycles .pdf