Edge-Disjoint Paths Count

Problem

Compute the maximum number of edge-disjoint paths between s and t in an undirected graph.

By Menger's theorem this equals the minimum edge cut size. Give every edge unit capacity and run max flow from s to t. edges is a list of [u, v] pairs. Return the flow value.

Hint

Unit edge capacities make max flow equal the edge connectivity between s and t.

Test cases

case 1

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

expected: 2

case 2

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

expected: 2

case 3

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

expected: 1

Starter codePython

def max_edge_disjoint_paths(n, edges, s, t):
    # Your code here
    pass

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