This is a question from the book The Algorithm Design Manual by Steven Skiena, Page no- 201.
Articulation vertex : An articulation vertex of a graph (undirected) G is a vertex whose deletion disconnects G.
Given : Graph (undirected) $G = (V,E)$
Find : A vertex not an articulation vertex
Here is how i tried. I know a brute force way to solve the problem. A1 is the brute force algorithm given below.
- Pick a vertex say $v$.
- Delete the vertex temporarily from $G$ (say $G'$ is a new graph).
- Run DFS on $G'$.
- If graph $G'$ is connected return (V).
- Else repeat (step 1 to step 4) for all vertice of $G$.
Runtime : $O(V(V + E))$
For better running time algorithm i tried to come up with a claim.
My Claim : A vertex is an not articulation vertex if in a DFS tree it involves in a back edge.
If the above claim is true then i only need to run the DFS algorithm once that means running time $O(V + E)$. So I have two questions 1) Is the claim correct 2) find an efficient algorithm which runs in $O(V + E)$. time.