Vertex-Disjoint Paths Count (Menger)

Problem

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

By Menger's theorem this equals the minimum vertex cut size. Split each internal node into an in and out copy with capacity 1, make every graph edge infinite, and run max flow from s to t. Return the flow value.

Hint

Node splitting turns a vertex cut problem into an edge cut problem.

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]

expected: 1

case 3

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

expected: 2

case 4

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

expected: 0

Starter codePython

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

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