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)
