CS 180 Winter 2014
Homework 9 Solutions (2 pages) 1. We rst compute an integer maximum s t ow, consisting of edge-disjoint paths P1 , P2 , . . . , Pk . Now, for each i, we ping the nodes on Pi in binary-search fashion: we try the middle node; if it is reachable, we try the node 3/4 of the way along Pi , and if it is unreachable, we try the node 1/4 of the way along Pi . Since s is reachable and t is not, and these are the endpoints of Pi , we can continue in this way until, after O(logn) pings, we have found an edge (v, w) on Pi for which v is reachable and w is not. Doing this for each i, we nd k such edges using O(klogn) pings. Since the adversary only deleted k edges, we have now found all of them. We delete these edges from G, and then use breadth-rst search to determine all nodes reachable from s. The remaining nodes form the unreachable set that we were trying to determine. 2. We dene a directed graph G = (V, E ) with nodes s, v1 , v2 , . . . , vn , where our sink t will correspond to v1 . Dene an edge (s, vi ) of capacity bi , and edge (vi , vj ) and (vj , vi ) of capacity pij for each pij > 0. Dene B = i bi . Now, let (X, Y ) be the minimum s v1 cut in G. The capacity of (X, Y ) is c(X, Y ) =
i Y
bi +
iX,j Y
pij bi + pij
iX,j Y iX bi
=B
i X
Thus, nding a cut of minimum capacity is the same as nding a set X maximizing iX,j / Y pij . 3. We dene a ow network G = (V, E ) as follows.
There is a source s, vertices v1 , . . . , vn for each person vertices w1 , . . . , wm for each advertiser, and sink t. There is an edge of capacity 1 from vi to each wj for which person i belongs to a demographic group that advertiser j wants to target. There is an edge with a capacity of 1 from s to each vi ; and for each j , there is an edge with lower bound rj from wj to t. Finally, the source has a demand of j rj , and the sink has a demand of j rj . All other nodes have demand 0. Now, if there is a valid circulation in this graph, then there is an integer circulation. In such a circulation, one unit of ow on the edge (vi , wj ) means that we show an ad from advertiser j to person i. With this meaning, each advertiser shows their required number of ads to the appropriate people. Conversely, if there is a way to satisfy all the advertising contracts, then we can construct a valid circulation as follows. We place a unit of ow on each edge (vi , wi ) for which i is shown an ad from advertiser j ; we put a ow on the edge (wj , t) equal to the number of ads shown from advertiser j ; and we put a unit of ow on each edge (s, vi ) for which person i sees an ad.
Thus, there is a valid circulation in this graph if and only if there is a way to satisfy all the advertising contracts; and the ow values in an integer-valued circulation can be used, as above, to decide which ads to show to which people. 4. Consider the cut (A , B ) found by performing breadth-rst search starting from s on the residual graph Gf at the end of any maximum ow algorithm. We claim that a node v is upstream if and only if v A . Clearly, if v is upstream, then it must belong to A ; since otherwise, it lies on the sink-side of the minimum cut (A , B ). Conversely, suppose v A were not upstream. Then there would be a minimum cut (A , B ) with v B . Now, since v A , there is a path P in Gf from s to v . Since v B , this path must have an edge (u, w) with u A and w B . But this is a contradiction, since no edge in the residual graph can go from the source side to the sink side of any minimum cut. A completely symmetric argument shows the following. Let B denote the ndoes that can reach t in Gf (performing breadth-rst search starting from t on reversed edges), and let A = V B . Then (A , B ) is a minimum cut, and a node w is downstream if and only if w B . Thus, our algorihm is to compute a maximum ow f , build Gf , and use breadth-rst search to nd the sets A and B . These are the upstream and downstream nodes respectively; the remaining nodes are central.
