Hi everyone!

Suppose we have a weighted graph with N vertices and two vertices S and T are given. We have to remove some edges from the graph in order to separate the given vertices (after removing the edges, there should be no path from S to T). Suppose the cost is the sum of the edges weights. Find the minimum cost to achieve this.

In case of tie (more than one way to remove edges, obtaining the minimum cost), remove the minimum number of edges.

I know that finding the minimum cost of the cut can be solved via Max Flow, but how can we handle the ties? Sure, we can find the cut-set, but the cut-set cardinality isn't always the answer.

Is there a good way to handle these cases?

Thanks!