Least number of edges that appear in every path

Question

I need to find the least number of edges in a graph that appear in every path from the first vertice to the last. For example - in the image if the first vertice is V0 and the last vertice is V8 then the least number of vertices that appear in every path from V0 to V8 is 2 and they are the ones in green (or in place of V6-V8 could have been V0-V3 or V3-V6).

Example image:

Been searching for a while but can't find (or think of) any algorithm to do this...

Answer 1

Your question is equivalent to finding a minimum s-t cut in the graph, since this cut gives the smallest set of edges that, if removed, disconnect s and t. This is the same as saying that every path goes through some edge in the minimum cut.

There are many algorithms for finding minimum s-t cuts. For example, the max-flow min-cut theorem states that the value of a max flow from s to t (if each edge has unit capacity) has the same flow as the number of edges in the min s-t cut. Consequently, any max-flow algorithm, such as Ford-Fulkerson or Edmonds-Karp, can be used to directly compute the cost of a min cut. From there, it's easy to recover the min cut by finding all edges reachable from s in the residual graph and taking all edges that have one endpoint in this set and another endpoint in the complement.

Hope this helps!