Prune graph to detect cycles: better than DFS?

Question

By pruning a undirected graph G, I mean iteratively removing all leaves (nodes of degree 1) together with the incident edge from a graph until you are left with a single node (G contained no cycle) or at least 2 edges (G contains a cycle). This is also called the 2-core of the graph.

Isn't this an easier algorithm for detecting cycles than the usually suggested DFS?

It would also work on directed graphs by pruning nodes with only ingoing edges.

Answer 1

One of the advantages of DFS is that it's a single algorithm that does lots of things. By the time you've implemented it five times, you will not think of anything else as an easier algorithm :) It will also find a cycle, whereas pruning leaves will in some cases only detect whether a cycle is present or not.

However, if that's all you need, the pruning algorithm can also be used. We have to be careful about how we implement it so that it's competitive with DFS. In general, DFS takes $O(|E|)$ time to go through the whole graph; however, it is guaranteed to find a cycle in $O(|V|)$ time, if one exists.

It is tempting to start the pruning algorithm by computing the degree sequence of the graph. However, if we naively do that, then we'll have taken $O(|E|)$ time just for that first step, when the graph is dense! This is easy to avoid, if we're careful: as you're computing vertex degrees, keep track of the total number of edges processed, and stop if $|E| \ge |V|$. In that case, we already know there will be a cycle - and if $|E| < |V|$, then we compute the degree sequence in $O(|V|)$ time.

Past that step, an outline of how we might finish the algorithm in $O(|V|)$ time is to:

• Go through all the vertices one by one in the main loop.
• Whenever you find a vertex of degree $1$, prune it and immediately go to its only neighbor - to update its adjacencies and check if that neighbor now has degree $1$. This might have to be repeated several times. When you're done, go back to where you were in the main loop.
• Vertices of degree $0$ should be pruned as well, though we don't have to do anything special with those.
• Once the main loop is finished, there is a cycle iff not all vertices have been pruned.

Computing the degree sequence in advance is not actually necessary. It is possible to combine that with the main loop: whenever we look at a vertex, all we need to do is test if it has degree $0$ or $1$, which can be done in $O(1)$ time without computing its degree.

I do not think this is particularly simpler than DFS, but it is a viable alternative.