Remove All Cycles

Question

Given a connected undirected graph $ G (V , E) $ and given that there exists a vertex $V_i$ such that removing it
(i.e, removing vertex and edges through it) makes the graph $ acyclic $ .
Is it possible to find $V_i$ in linear time ?
I have tried using the concepts of Articulation points and Bridges. One approach is removing each vertex and checking cycles and replacing it back if not acyclic which is a quadratic time algorithm and intuitive. How to find $V_i$ in linear time wrt edges?

Answer 1

First we can begin by using DFS to find a cycle $C$: either we succeed, or the graph is a tree and we can remove any vertex.

Once $C$ is found, then for every vertex $v$ on $C$, we can do another DFS starting at that vertex, but ignoring the cycle edges. We will either get a tree component rooted at $v$, or find another path back to $C$, ending at some vertex $w$.

In the second case, either $v$ or $w$ needs to be removed to make the graph acyclic, and we can check both possibilities in linear time. (Sometimes, both are valid choices.)

If there are no paths out of $v$ back to $C$, then we continue checking all the other vertices along $C$. If we don't find a path back to $C$ from any of them, then $C$ is the only cycle in the graph, so deleting any vertex on $C$ will work.

Note that in cases where we don't find a path back to $C$, we are checking a set of edges we'll never see again. So together, all the searches starting at vertices on the cycle take at most $O(|E|)$ time.