Question

Say that 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.

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 the algorithm correct? If it is not, how should we change it to be correct?

Does this algorithm work for the directed case? If yes, explain and if not explain why not.

Answer 1

No this approach will not work. The reason is that flow from v to Z via node t and the flow from v to Z via node s may share some common vertex and we want simple path without any vertex sharing.

To make this algorithm work, we have to simply add a flow constraint that every vertices in graph , amount of flow passed through it should be almost 1 unit. If we impose this constrain then path from v to Z via s and v to Z via t will be vertex disjoint and hence the path returned by them will be simple path and hence it 2 unit flow is there from v to Z then the required solution is met.

No this approach will not work for directed graph because even if flow value of 2 unit is there from v to Z and hence two vertex disjoint paths exist from s to Z, still this does not means that there exist path from s to v because it's directed graph while in undirected case, path from v to s exist also mean that path from s to v exist, this does not always happen in directed graph. Hence this approach will not work.

Hence this algorithm is correct.

Please comment for any clarification.