### snacache's blog

By snacache, history, 6 years ago,

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!

• +16

 » 6 years ago, # |   +92 add eps to all edge weights?
 » 6 years ago, # |   0 1 — Maxflow 2 — Build a new network where the saturated arcs will have capacity 1 and the other arcs will have capacity oo 3 — Maxflow 
 » 6 years ago, # |   +21 there is a problem like this in the USACO training pages chapter 4 called "Pollutant Control"to solve it multiply the capacity of each edge by (number of edges in the network + 1) and subtract 1 (c_new = (E + 1)*c_old — 1) and run maxflow why this works is simple the new maxflow is equal to old_maxflow * (E + 1) — number of edges used ,hence we get minimum number of edges .. why (E + 1) because it's the minimum number such that the -1 that accounts for the number of edges doesn't change the original paths (it's supposed only to break ties between paths with equal augmenting capacity)
•  » » 6 years ago, # ^ |   0 Interesting! I will try this. Thanks :)
•  » » 6 years ago, # ^ |   0 Sorry, maybe I didn't understand.Suppose I have this graph, there are five vertices and five edges, the source is 1 and the sink is 5:1 -> 2 (1)1 -> 3 (1)2 -> 4 (1)3 -> 4 (1)4 -> 5 (2)Where (x) means this edge has capacity x.The maxflow in this network is 2, if I multiply every edge with (E+1)=6 and subtract 1, then the graph will be:1 -> 2 (5)1 -> 3 (5)2 -> 4 (5)3 -> 4 (5)4 -> 5 (11)The maxflow in this network is 10, so, old_maxflow*(E+1) = 2*6 = 12 — number_of_edges = 10, number_of_edges = 2But the mincut with minimum size is given removing the edge between 4 and 5!Is my example wrong?
•  » » » 6 years ago, # ^ |   +5 You should add 1 to the capacity after multiplying, not subtract.
•  » » » » 6 years ago, # ^ |   +5 It worked! I was trying to solve this problemI didn't know there was a problem like this in USACO. But USACO version is more difficult because you must print the cut, breaking ties lexicographically.Thanks Noureldin and fofao_funk
•  » » » » » 6 years ago, # ^ |   0 Just out of curiosity: what max flow algorithm did you use to solve the problem? The constraints seem too high for edmonds karp, for example...
•  » » » » » » 6 years ago, # ^ |   0 Dinic should pass i believe, maybe with scaling
•  » » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 I used edmonds karp. Perhaps the test cases don't make the algorithm reach the worst case!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 sorry for the mistake it's +1 not -1 .. this way the new maxflow = oldflow * (E + 1) + #cut edges
•  » » 6 years ago, # ^ |   0 hello, for this problem we also need to print the edges with the lowest index, how to handle that?