Menu
I tried the following :
1) DFS, keeping track of level of each vertex in my DFS tree
2) Each time a back edge (x,y) is seen, I calculate cycle length = level[x] - level[y] + 1, and save it if it is smaller than the shortest
Can someone tell a counter example for which this approach is wrong ?
What could be a better way to find shortest cycle in undirected graphs ?
Thanks.
834
Undirected graphs and BFS. The key idea is that a shortest cycle is comprised of a shortest path between two vertices, say v and w, that does not include edge v-w, plus the edge v-w. We can find the shortest such path by deleting v-w from the graph and running breadth-first search from v (or w).
The standard baseline algorithm for finding a cycle base for an undirected graph is this : Build a spanning tree and then for each edge which is not part of the tree build a cycle from that edge and some edges on the tree. Such cycle must exist because otherwise the edge would be part of the tree.
If e has one end in X and the other end in Y then (X, Y) is a bipartition of G. Hence, assume that u and v are in X. If there were a path, P, between u and v in H then the length of P would be even. Thus, P + uv would be an odd cycle of G.
You cannot use DFS to find a shortest circle. We can easily create a counter example, where DFS leads finds only the longest circle. Lets have a look at the following graph:
As you can see we have nine nodes. If we start at the leftmost node A, the following DFS level could be possible:
We have two back edges while iterating:
(B , A), therefore we found a circle with length 8(D , A), therefore we found a circle with length 8However, the shortest circle has length 5. It's shown in blue in the next picture, whereas one of the previously found circles is shown in red:
You didn't see the blue circle because your DFS path doesn't contain it. Dagupa et al also mention this behaviour in their book:
But it also means that DFS can end up taking a long and convoluted route to a vertex that is actually very close by.
Well, that's not entirely true, one can use BFS (see next subsection), but you cannot use your formula. Take the following graph:
No fancy picture for this graph yet. Every "o" is a node. o---o | | +-------o---o-------+ | | o----o----o----o----o
Lets see what levels are possible in BFS. If I start at the node in the middle, I get the following levels:
5~~~5 ~~~ are back-edges | | +-------4~~~4-------+ | | 3----2----1----2----3
And if I start at the left node, I get the following levels:
3~~~4 | | +-------2---3-------+ | | 1----2----3----4~~~~4
Therefore, you cannot use your level formula.
Although not efficient, using an all-pair shortest path algorithm and checking the distance (i,i) for every node is a valid solution.
89
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
