Fold-Fullkerson’s theorem for vertices

Task number: 3978

Formulate and prove an analogy of the Ford-Fulkerson theorem for networks with capacities of vertices instead of edges.

  • Solution

    A network with vertex capacities has a flow of size \(k\) is and only if the minimum vertex cut separating \(s\) and \(t\) has size \(k\).

    Proof: Replace each edge with a pair of opposite edges (a digon) with an unbounded capacity. We split each vertex \( u \) into two vertices \( u’\) and \( u’’\), that \( u ’\) is incident with all edges incoming to \( u \) and similarly \( u’ ’\) with all outgoing ones. We add the edge \( (u’, u’’) \) and assign it the capacity that the vertex \( u \) had in the original graph.

    The maximum flow in the new graph corresponds to an edge cut in the new graph and it corresponds to a vertex cut in the original graph. Moreover there is a direct correspondence between flows in the old and in the new graph (bijective upto ciculation on the digons)

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email