Complexity

$E$ is the set of all the edges in the graph, and $V$ is the set of all the vertices in the graph.

Theorem: The complexity of the algorithm in the best case is $O(\vert E\vert)$ and in the worst case is $O(\vert E\vert\vert V\vert)$

Proof. The cyclic edge detector algorithm presented is based on a depth first search traversal of a graph, accordingly it must traverse every edge in the graph once, which is $O(\vert E\vert)$ . When a forward edge is encountered in the search, the algorithm finds the highest cyclic ancestor, that is, the cyclic ancestor with the earliest timestamp. This is achieved by traversing a path through cyclic ancestors until the highest cyclic ancestor is found. Traversing a path comprised of cyclic ancestors has the potential to visit every vertex in the graph, therefore the complexity of this traversal is $O(\vert V\vert)$ . The worst case is if the majority of edges in the graph were forward edges, as this would require a search for the highest cyclic ancestor potentially for every forward edge traversed. This results in a worst case time complexity of $O(\vert E\vert\vert V\vert)$ . The best case is when there are no forward edges, for which the algorithm would behave like a normal depth first search. The time complexity for the best case is that of depth first search which is $O(\vert E\vert)$ .

An example worst case is show in Fig. . The tree edges are solid purple edges, the back edges are dashed purple edges, and the forward edges are dotted green edges between vertices $\{1,2,3,4,5\}$ and 7. After traversing through the graph from vertex 1 to vertex 6, the algorithm traverses a tree edge to vertex 7, and then a back edge to vertex 6. Thus the cyclic ancestor for vertex 7 is vertex 6, as shown in Fig . The cyclic ancestor pointer is indicated by the widely dashed blue line between vertices 7 and 6. As the algorithm traverses the back edges $(6, 5), (5, 4)$ etc, the cyclic ancestors will be set to be the immediate vertex above, with vertex 0, being it's own cyclic ancestor. When a forward edge $(5, 7), (4, 7)$ etc is traversed, the chain of cyclic ancestors will have to be traversed in order to find the highest cyclic ancestor. Doing this causes vertices to be visited, several times for each forward edge, adding the upper bound time complexity of |V|. Ultimately vertex 7 reassigns it's cyclic ancestor to vertex 0 as show in in Fig. . From this case, it can be determined that if the majority of edges in a graph were forward edges, the upper bound for the worst case is as stated, $O(\vert E\vert\vert V\vert)$ . $\qedsymbol$

Figure: A graph showing two stages of a traversal using the cyclic edge detector algorithm. The solid purple edges are tree edges, the dashed purple edges are back edges and the dotted green edges are forward edges. The widely dashed blue line indicates the current cyclic ancestor for vertex 7, during the two stages shown of the search.

[] []