6.4.1. Finding a Feasible Flow

To find a feasible flow or decide that no such flow exists, we can use any maximum-flow algorithm: We transform \(G\) into a network \(H\) by adding two vertices \(s\) and \(t\) to \(G\). We add an edge of capacity \(b_x\) from \(s\) to every supply node \(x\) and an edge of capacity \(-b_x\) from every demand node \(x\) to \(t\). The edges of \(G\) have the same capacity in \(H\) as in \(G\).

Observation 6.15: There exists a feasible flow in \(G\) if and only if \(H\) has a maximum \(st\)-flow \(f'\) with \(F'_s = \sum_{x \in G} \max(0, b_x)\). If there exists such an \(st\)-flow in \(H\), then the flow \(f\) defined as \(f_e = f'_e\) for all \(e \in G\) is a feasible flow in \(G\).

Exercise 6.4: Prove Observation 6.15.