SuperSheep's blog

[Help] How do you recover a set of edges that form the minimum cut after running maximum flow?
By SuperSheep, history, 22 months ago, In English

I figured you'd have to check the edges that are saturated, and if there's a path of saturated edges with the same capacity, choose any of them. But I'm having trouble on cases where there may be many of those paths or the saturated edges are connected by non-saturated edges with higher capacity in between.

I came up with checking every path that has at least one saturated edge, but I think that would be too slow as it may check too many edges just to get one of the saturated ones, in something like $$$O(|minCutEdges| \cdot E)$$$.

How do you do it efficiently?

If it's relevant, I'm trying to solve this problem (can find the optimal profit but can't print the solution): szkopul — Travel Agency (biu)

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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SuperSheep (previous revision, new revision, compare).

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

After you've run your flow algorithm on the graph, the ending point will not be reachable from the starting point (if only positive weight edges are traversed). Let $$$A$$$ be the set of all nodes reachable from the starting point and let $$$B$$$ be the set of all nodes not reachable from the starting point. Now, the minimum cut is formed exactly by all edges satisfying all following properties:

  • The edge was one of the original edges
  • The edge starts from a node in A
  • The edge ends in a node in B
  • The edge has weight zero after running the flow algorithm.

Finding all such edges shouldn't be too difficult. If you can't come up with anything, I can help more.

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

    Thanks a lot!

    That was a very clear and helpful explanation. I get it now :)

    → Reply