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.

Po

Does an ordinary BFS implementation find non-simple paths, getting stuck in cycles?? – Hearing

@clwhisk You can remove the edge e, and find a path from x to v and a path from u to y using BFS for each, notice that the BFS will find a simple path, this can be proven and I assume you've proved it in lectures, so for the problem of finding regular path just do the above things and the path will be (x -> ... -> v -> u -> ... -> y) – Po

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.

Vulpine

@CSStudent Note that since you need to find at most 2 augmenting paths, Edmonds-Karp takes linear time. – Repute

I think this allows vertices to appear multiple times, which allows non-simple paths. E.g., the graph {xb, yb, bu, bv, uv} has no solution due to a bottleneck at b, but (my interpretation of) your algorithm would indicate the paths xbu and ybv, implying the non-simple path xbuvby. – Novotny

@PeterdeRivaz Thank you, I will check this answer later and will confirm if it was found to be true. – Po