Given an undirected graph with non-negative edge weights, and two vertices $s,t$ in the graph. I would like to find the minimal cut such that $s$ and $t$ are on different sides of the cut.
For example I have a graph describing the network of roads connecting Berlin and Munich and I want to find the minimal cut such that Berlin and Munich fall on different sides of the cut.
I know of an algorithm for global minimal cut (Karger), which wouldn’t guarantee that $s$ and $t$ are not on the same side of the cut. The best thing I managed to find was this article for finding the s-t min-cut of a directed graph (flow network).
I think I can use the flow network algorithm to solve the problem by doing the following:
- Make my undirected graph directed by replacing each edge with two directed edges.
- Apply the “minimum s-t cut in a flow network” algorithm on step one’s graph to find all edges of the directed s-t min-cut.
- For the undirected case the s-t min-cut consists off all edges where at least of its directed was in step two’s min-cut.
Is there a more efficient algorithm for this problem specifically for undirected graphs?