How to find if there is a simple path from vertex x to vertex y that includes the edge e

Question

so I faced this question and I hope that someone can help me in it.

Given an undirected graph G = (V, E), 2 vertices x,y and an edge e = (v,u).

Suggest an algorithm to find if there's a simple path from x to y that includes the edge e.

So the focus here is on the simple path and not a regular path, for a regular path it's an easy problem using the BFS to search a path from x to v and a path from u to y.

I know that the problem can be solved using the max-flow approach but I just don't recognize how to build a new graph that can implement a max-flow algorithm on it so it tells whether the above criterion is achieved or not, I hope for help.

Thanks in advance.

Answer 1

Without sharing edges (edge-independent)

You could solve max flow with +1 sources at x and y, and -1 sinks at u and v.

Remove the edge e, and set all other edges to capacity 1.

A simple path from x to y via edge e exists if and only if you can find a flow of 2 in this new max flow problem.

Without sharing vertices (vertex-independent i.e. simple path)

Split each vertex v[i] in the original graph into two vertices, a[i] and b[i].

For each undirected edge between v[i] and v[j] in the original, add directed edges b[j] to a[i] and b[i] to a[j] with capacity 1.

Also add a directed edge from a[i] to b[i] with capacity 1 for each vertex v[i].

The idea is that flow must always arrive at an a[i] vertex, and leave from a b[i] vertex, after passing through the capacity 1 bottleneck from a[i] to b[i]. This ensures that each vertex can only be used once.

With this new graph, proceed as for the edge-independent case.