snacache's blog

Minimum Cut with Cut-Set of minimum size?
By snacache, history, 7 years ago, In English

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!

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +92 Vote: I do not like it

add eps to all edge weights?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
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
→ Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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)

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Interesting! I will try this. Thanks :)

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You should add 1 to the capacity after multiplying, not subtract.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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...

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Dinic should pass i believe, maybe with scaling

            → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            I used edmonds karp. Perhaps the test cases don't make the algorithm reach the worst case!

            → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      sorry for the mistake it's +1 not -1 .. this way the new maxflow = oldflow * (E + 1) + #cut edges

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hello, for this problem we also need to print the edges with the lowest index, how to handle that?

    → Reply