CSOR W4246 { Fall, 2017
hw3-t solutions
1. i. Suppose there is a feasible circulation f. By definition
X v2V
d(v) = X
v2V
fin(v) − fout(v):
In this sum, every edge (u; v) appears twice: once as an outgoing edge fr
...
CSOR W4246 { Fall, 2017
hw3-t solutions
1. i. Suppose there is a feasible circulation f. By definition
X v2V
d(v) = X
v2V
fin(v) − fout(v):
In this sum, every edge (u; v) appears twice: once as an outgoing edge from u and once
as an incoming edge into v. Hence
X v2V
d(v) = 0:
It follows that
X
v:d(v)>0
d(v) = − X
v:d(v)<0
d(v):
ii. Construct the following flow network G0 in polynomial-time:
a) Add a super source s∗ and a super sink t∗.
b) Add one outgoing edge from s∗ to s, for every s 2 S with capacity −d(s).
c) Add one outgoing edge from t to t∗, for every t 2 T with capacity d(t).
We claim that there is a circulation that satisfies all demands in G if and only if there
is a max flow of value −Ps2S d(s) in G0.
Let D = −Ps2S d(s) = Pt2T d(t).
()) Given a feasible circulation f in G, in G0 send flow −d(s) across (s∗; s) for every
s 2 S and flow d(t) across (t; t∗) for every t 2 T. This is a valid flow in G0, its value
is D and its value equals the capacity of the cut (s∗; V − fs∗g) (and the capacity of
the cut (V − ft∗g; t∗), hence it is maximum.
(() Conversely, suppose there is a maximum flow of value D in G0. Since the value
of the flow equals flow out of s∗ and the capacity of the cut (s∗; V − fs∗g) is D,
every edge out of s∗ is saturated. Similarly, the value of the flow equals flow into t∗
and the capacity of the cut (V − ft∗g; t∗) is D, so every edge into t∗ is saturated.
Thus, if we delete all (s∗; s) and (t; t∗) edges, we obtain a circulation f such that
fin(v) − fout(v) = d(v) for every
[Show More]
