Least number of edges appearing on each path
I need to find the smallest number of edges in a graph that appear in every path from the first vertex to the last. For example - in the image, if the first vertex is V0 and the last vertex is V8, then the least number of vertices that appear in each path from V0 to V8 is 2 and they are green (or instead of V6-V8 it could be V0-V3 or V3-V6).
Image example:
Searched for a while but could not find (or think) any algorithm for this ...
source to share
Your question is equivalent to looking for the smallest cut st in the graph, since that cut yields the smallest set of edges that, if removed, cut off s and t. This is the same as saying that each path passes through some edge in the minimum cut.
There are many algorithms for finding the minimum cuts st. For example, the max-stream min-cut theorem states that the value of the maximum flow from s to t (if each edge has unit capacity) has the same flow as the number of edges in min st cut. Therefore, any maximum flow algorithm such as Ford-Fulkerson or Edmonds-Karp can be used to directly calculate the cost of the minimum cut. From there it is easy to reconstruct the minimal cut by finding all the edges reachable from s in the residual graph and taking all the edges that have one endpoint in this set and another endpoint in the complement.
Hope this helps!
source to share