Search code examples
algorithmmax-flowundirected-graph

how to use Dinic's algorithm to find min-cut edges in undireted graph?

I am looking for an algorithm, when a given two nodes 's' and 't' in a undiredted graph, to find min-cut edges, which partitions the graph into two A and B, 's' will in A and 't' will in B.

I see most people suggesting for Ford–Fulkerson algorithm to for that task, at here. I am thinking is that is it possible to use Dinic's algorithm for it. Since Dinic's algorithm can be speed up with dynamic tree. Because I want to find min-cut edges with fastest way possible.

which algorithm is faster for to find min-cut edges in a huge undirected graph?

I would like to hear some advice while I am looking into the details for these algorithm.

Thanks in advance

Solution

  • Basically, any algorithm which solves the maximal flow, also solves the minimal cut. Once you have the flows, find the residual flow graph. In this graph, run BFS from the source s. The min cut is just the set of edges (u, v) for which u is reachable from s, and v is not.

    Since Dinic is only O(V2E) as opposed to FF's Θ(E2V), then it will be faster, in general.

    The cost of finding the residual flow graph and running BFS is negligible, in this case.