Answered You can hire a professional tutor to get the answer.
We have an undirected graph G(V, E) and a pair of vertices s, t and a vertex v that we call a a desired middle vertex .
We have an undirected graph G(V, E) and a pair of vertices s, t and a vertex v that we call a a desired middle vertex . We wish to find out if there exists a simple path (every vertex appears at most once) from s to t that goes via v.
(a) Say we check if there is a simple s to v path on the undirected graph, and we check if there is a simple v to t path in the undirected graph. If the answer for questions is yes, we output "There is a simple path from s to t that goes via via v". Else we output "There is a no simple path from s to t that goes via via v". Is the algorithm correct? If so give an analysis. Otherwise, show an example graph for which the algorithm produces a wrong solution.
(b) We have to create a flow network by making v a source. Add a new vertex Z as a sink. Join s, t with two directed edges of capacity 1 to the sink Z. Replace every edge in the graph by two anti parallel edges. Give all edges capacity 1, Check if there is a flow from v to z of value 2. If there is we answer yes on the path question, and else we answer no. Is s the algorithm correct?
(c) If it is not, how should we change it to be correct?
(d) Does this algorithm work for the directed case? If yes, explain and if not explain why not.
Please give the time complexity for the algorithm
