Cut-Set Bound

Problem

Return the min-cut capacity of a directed network given the capacity matrix capacity[i][j], a source and a sink. A cut is a set S of vertices that contains the source but not the sink; its capacity is the sum of capacities of edges from S to its complement. Return the minimum over all cuts.

Hint

Max-flow equals min-cut, so the bottleneck cut bounds the achievable rate.

Test cases

case 1

in: [[[0,2,3],[0,0,4],[0,0,0]],0,2]

expected: 5

case 2

in: [[[0,5,0],[0,0,5],[0,0,0]],0,2]

expected: 5

case 3

in: [[[0,3,0,0],[0,0,2,0],[0,0,0,3],[0,0,0,0]],0,3]

expected: 2

case 4

in: [[[0,1,1],[0,0,0],[0,0,0]],0,2]

expected: 1

Starter codePython

def cut_set_bound(capacity, source, sink):
    # Your code here
    pass

4 test cases · run your code against them in the editor