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!
add eps to all edge weights?
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)
Interesting! I will try this. Thanks :)
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 = 2
But the mincut with minimum size is given removing the edge between 4 and 5!
Is my example wrong?
You should add 1 to the capacity after multiplying, not subtract.
It worked! I was trying to solve this problem
I 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
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...
Dinic should pass i believe, maybe with scaling
I used edmonds karp. Perhaps the test cases don't make the algorithm reach the worst case!
sorry for the mistake it's +1 not -1 .. this way the new maxflow = oldflow * (E + 1) + #cut edges
hello, for this problem we also need to print the edges with the lowest index, how to handle that?