Description
Problem: Let G = (V, E) be a directed acyclic graph with two specified vertices s and t. A vertex v ∈{/ s, t} is called an (s, t)-cut vertex if every path from s to t passes through v. If G has n vertices and m edges, then design a polynomial-time algorithm that computes all the (s, t)-cut vertices of G.
Explain the main steps of the algorithm. Give a precise explanation of the explicit polynomial running time of your algorithm. You can write either the pseudocode or the plain text description of your algorithm. But make sure to write proper explanation so that your claimed running time is consistent with your algorithm.
For instance, if your algorithm runs in O(nm)-time, then explain why it is O(mn). Similarly, if your algorithm runs in O(m+n)-time, then explain why your algorithm runs in O(n+m)-time.
Finally, give a short explanation why your algorithm correctly finds all the cut vertices.
Example: If the directed graph is as per the figure below, then your algorithm should output all the red colored vertices.
1
