Optimizing Flow Networks: Problems and Solutions
[9] Patient Allocation to Hospitals as a Flow Network
We build the following flow network. There is a node vi for each patient i, a node wj for each hospital j, and an edge (vi, wj) of capacity 1 if patient i is within a half-hour drive of hospital j. We then connect a super-source s to each of the patient nodes by an edge of capacity 1, and we connect each of the hospital nodes to a super-sink t by an edge of capacity n/k. We claim that there is a feasible way to send all patients to hospitals if and only if there is an s-t flow of value n. If there is a feasible way to send patients, then we send one unit of flow from s to t along each of the paths s, vi, wj, t, where patient i is sent to hospital j. This does not violate the capacity conditions, in particular on the edges (wj, t), due to the load constraints. Conversely, if there is a flow of value n, then there is one with integer values. We send patient i to hospital j if the edge (vi, wi) carries one unit of flow, and we observe that the capacity condition ensures that no hospital is overloaded. The running time is the time required to solve a max-flow problem on a graph with O(n+k) nodes and O(nk) edges.
[10] Restoring Capacity Conditions in a Flow Network
We will assume that the flow f is integer-valued. Let e* = (v, w). If the edge e* is not saturated with flow, then reducing its capacity by one unit does not cause a problem. So assume it is saturated. We first reduce the flow on e* to satisfy the capacity conditions. We now have to restore the capacity conditions. We construct a path from w to t such that all edges carry flow, and we reduce the flow by one unit on each of these edges. We then do the same thing from v back to s. Note that because the flow f is acyclic, we do not encounter any edge twice in this process, so all edges we traverse have their flow reduced by exactly one unit, and the capacity condition is restored. Let f’ be the current flow. We have to decide whether f’ is a maximum flow, or whether the flow value can be increased. Since f was a maximum flow, and the value of f’ is only one unit less than f, we attempt to find a single augmenting path from s to t in the residual graph Gf. If we fail to find one, then f’ is maximum. Else, the flow is augmented to have a value at least that of f; since the current flow network cannot have a larger maximum flow value than the original one, this is a maximum flow.
[11] Counterexample to a Claim about Augmenting Paths
The statement is false and the following is a counterexample to it. Let us be given a number b > 1 (we will without loss of generality assume that it is an integer, otherwise we will round it up). We consider the following graph. It has 2(b+1)+2 vertices: source s, sink t, and vertices u1,u2,..,ub+1 that have an edge coming from the source and vertices v1,v2,..,vb+1 that have an edge going into the sink. There is also an edge from ui to vi and from vi to ui+1. All the edge capacities are 1. Now assume that the first augmenting path was the path s->u1 ->v1-> u2 -> v2.. -> ub+1 vb+1 —> t. Then since all the backward edges are deleted from the residual graph according to the super-fast algorithm, the residual graph would contain no path from s to t, and therefore our final flow would equal 1. But there is a flow of value b+1 by using the horizontal edges (that is ui -> vi). Therefore we failed to reach within b of the optimum. Notice that for different b‘s we would be considering different graphs, but we are allowed to do this since the problem asks whether there exists a universal b that is independent of the choice of the flow graph G.
[12] Reducing Flow by Deleting Edges in a Cut
If the minimum s-t cut has size <=k, then we can reduce the flow to 0. Otherwise, let f>k be the value of the maximum s-t flow. We identify a min s-t cut (A, B), and delete k of the edges out of A. The resulting subgraph has a maximum flow value of at most f-k. But we claim that for any set of edges F of size k, the subgraph G’=(V,E—F) has an s-t flow of value at least f—k. Indeed, consider any cut(A, B) of G’. There are at least f edges out of A in G, and at most k have been deleted, so there are at least f—k edges out of A in G’. Thus, the minimum cut in G’ has value at least f—k, and so there is a flow of at least this value.
[13] Node Capacities and the Max-Flow Min-Cut Theorem
For each node v other than the source and sink, we replace it with two nodes, vin and vout. All edges that used to come into v now go into vin, and all edges that used to come out of v now go out of vout. All these edges have infinite capacity. (Or if is enough to choose a number larger than the sum of all node capacities.) Finally, there is an edge (vin, vout) of capacity cv. We consider flows from sin to tout in this new graph. Now, if there is a flow of value v in this new graph, then there is a flow of value v in the original graph that respects all node capacities: we simply use the flow obtained by contracting all edges of the form (vin, vout). Conversely, if there is a flow of value v in the original graph, then we can use it to construct a flow of value v in this new graph; the flow using v in the original graph will now pass through the edge (vin, vout) and it will not exceed this edge capacity due to the node capacity condition in the original graph. Thus, to compute a maximum flow subject to the node capacities, we simply compute a standard maximum flow in the new graph. Now, for the version of the Max-Flow Min-Cut Theorem for node-capacitated graphs. If we apply the standard Max-Flow Min-Cut Theorem to the new graph we constructed, it says that the maximum flow equals the minimum capacity of a cut. A minimum cut will only cut edges of the form (vin, vout) -cutting all such edges will separate sin from tout, and cutting any single other edge will produce a more expensive cut. Interpreted in the original graph, this corresponds to deleting a subset of the nodes, and defining the capacity of this deleted set to be the sum of the capacities of the deleted nodes. This shows that in a node-capacitated network, the value of the maximum flow is equal to the minimum capacity of a set of nodes whose deletion leaves no path from s to t.
[14] Escape Problem: Edge-Disjoint and Node-Disjoint Paths
(a) We turn G into a flow network as follows. Let k =|X|. We give each edge a capacity of 1, we add a super-source s with capacity-1 edges to each node in X, and we add a super-sink t with a capacity-k edge from each node in S. We then check whether the maximum s-t flow has a value of k. If so, then it has an integer-valued one and by deleting s and t, we get the desired set of disjoint paths from X to S. Conversely, if there is a solution to the escape problem, then by sending one unit of flow to each node in X, one unit of flow along each of the paths in the escape solution, and c units of flow to t from each node in S that is at the head of c paths, we get a flow of value k.
(b) We use the result of the previous problem on node-capacitated graphs. We again attach a source s to each node in X, and connect each node in S to a sink t. We now give each node in G a capacity of 1, and we give s and t each a capacity of k. By an argument strictly analogous to the one in (a), there is a flow of value k respecting the node capacities if and only if there is a solution to the escape problem with the stronger restrictions on nodes. A simple example of an instance where there is a solution under the constraints in (a) but not under the constraints in (b) is as follows. Let X = {x1, x2} and S = {s1, s2}; suppose G has nodes X U S U {v} for an additional node v, and edges (xi, v) and (v, sj) for i = 1, 2 and j = 1, 2.
[15] Dinner Schedule as a Bipartite Matching Problem
(a) Let G = (V, E) be a bipartite graph with a node pi E V representing each person and a node dj E V representing each night. The edges consist of all pairs (pi, dj) for which dj !E Si. Now a perfect matching in G is a pairing of people and nights so that each person is paired with exactly one night, no two people are paired with the same night, and each person is available on the night they are paired with. Thus, if G has a perfect matching, then it has a feasible dinner schedule. Conversely, if G has a feasible dinner schedule, consisting of a set of pairs S {(pi, dj)}, then each (pi, dj) E S is an edge of G, no two of these pairs share an endpoint in G, and hence these edges define a perfect matching in G.
(b) An algorithm is as follows. First, construct the bipartite graph G from part (a): it takes O(1) time to decide for each pair (pi, dj) whether it should be an edge in G, so the total time to construct G is O(n2). Now, let Q denote the set of edges constructed by Alanis. Delete the edge (pj,dk) from Q, obtaining a set of edges Q’. Q’ has size n — 1, and since no person or night appears more than once in Q’, it is a matching. We now try to find an augmenting path in G with respect to Q’, in time O(|E|)= O(n2). If we find such an augmenting path P, then increasing Q’ using P gives us a matching of size n, which is a perfect matching and hence by (a) corresponds to a feasible dinner schedule. If G has no augmenting path with respect to Q’, then by a theorem from class, Q’ must be a maximum matching in G. In particular, this means that G has no perfect matching, and hence by (a) there is no feasible dinner schedule.
[16] Advertising Contracts as a Circulation Problem
We define a flow 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 — SUMj rj, and the sink has a demand of SUMj 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 flow 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 flow on each edge (vi, wj) for which i is shown an ad from advertiser j; we put a flow on the edge (wj, t) equal to the number of ads shown from advertiser j; and we put a unit of flow 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 flow values in an integer-valued circulation can be used, as above, to decide which ads to show to which people.
[17] Finding Deleted Edges in a Flow Network
We first compute an integer maximum s-t flow, 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’s reachable, we try the node 3/4 of the way along Pi, and it it’s 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(log n) 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 find k such edges using O(k log n) 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-first search to determine all nodes reachable from s. The remaining nodes form the unreachable set that we were trying to determine.
[18] Matching Extension and Flow Networks
(a) We set up a flow problem. We define a new graph G’ for our flow problem by taking G and directing all edges from X to Y, and adding a super source s to the graph, and add edges (s, x) for all nodes x E X with capacity 1, and have each edge of G have capacity 1 also. We add a super sink t and add edges (y, s) for all nodes y that are not covered by the matching M. Now we define a flow problem where node s has a supply of |M|+k, node t has a demand of k, all nodes y E Y that are covered in M have a demand of 1. We claim that a flow satisfying these demands exists if an only if the matching M’ exists. If there is a flow in G’ satisfying the demands, then by the integrality theorem there is an integer flow f’. The edges e in G that have f'(e) = 1 form the desired matching M’. If there is a matching M’, then we can define a flow f’ in G’ as follows. For edges e=(x,y) we have f'(e)=1 if e is in M’ and 0 otherwise, we set f'(e)=1 for edges e=(s, x) if node x is covered by M’, and finally, we set f'(e)=1 for edges e=(y, t) if node y is covered by M’, but not covered by M. This satisfies all the demands. It takes O(m) time to build the flow network, and O(mC) = O(mn) time to determine whether the desired flow exists.
(b) For example, take a 4 node graph with two nodes on each side, and edges (x1, y1), (x1, y2) and (x2, y2). Let M have the single edge (x1, y2) and set k = 1. Then the solution exists, but only by deleting the edge (x1, y2), and reassigning y2 to x2.
(c) Consider the graph G’ analogous to the one we used in part (a), but connecting all nodes y E Y to the new sink t via an edge of capacity 1. Instead of using demands, we view this as a standard maxflow problem. We will show that there is a maximum matching that covers all nodes in Y that were covered by M. This implies that K1>=K2, and hence they are equal. The matching M gives rise to a flow of value |M| in G. Let f denote this flow. We use the Ford-Fulkerson algorithm, but instead of starting from the all-zero flow, we start from the integer flow f. This results in an integer maximum flow f’. The value of f’ is K2. We claim that the corresponding matching M’ covers all nodes in Y that are covered by matching M. A matching corresponding to an integer flow f in G’ covers exactly those nodes in Y for which f(e)=1 for s=(y, t). The statement above follows from the observation that for any node yEY and edge e=(y,t) if f(e)=1 and we obtain f’ by the Ford-Fulkerson algorithm starting from the flow f , then f'(e)=1 also. For a flow augmentation to decrease the value of the flow on an edge e, we would have to use the corresponding backwards edge in the augmenting path, but this backwards leaves t, and hence is not part of any simple s-t paths.
[19] Doctor Scheduling with Preferences and Constraints
We construct a flow network as follows. There is a node uj for each doctor j and a node vi for each day i. There is an edge (uj, vi) of capacity 1 if doctor j can work on day i, and no edge otherwise. There is a source s, and an edge (s, uj) of capacity |Lj| for each j. There is a sink t, and an edge (vi, t) of capacity pi for each i. Now we consider if there is an s-t flow of value SUM(i=1 to n)pi in this flow network. If there is then there is an integer-valued flow, and we can produce a set of lists {Li‘} from this as follows: assign doctor j to day i if there is a unit of flow on the edge (uj, vi). In this way, each doctor only works on days he or she finds acceptable, and each day i has pi working on it. Conversely, if there is a valid set of lists for the doctors, then there will be a flow of value SUM(i=1 to n)pi in the network: we simply raise one unit of flow on each path s–uj–vi–t, where doctor j works on day i. The total running time for this algorithm is dominated by the time for a flow computation on a graph with O(kn) edges, where the total capacity out of the sink is O(kn); thus, the total running time is O(k2n2).
(b) We take the previous flow network and add some nodes to it, modeling the requirements. For each doctor j, we add a “spill-over” node uj‘. There is an edge (uj‘,vi) of capacity 1 for each day i such that doctor j doesn’t want to work on i. There is an edge (s,uj‘) of capacity c for each j. Again we consider if there is an s-t flow of capacity SUM(i=1 to n)pi in this flow network. If there is, then there is an integer-valued flow, and we can produce a set of lists {Li‘} from this as follows: assign doctor j to day i if there is a unit of flow on the edge (uj, vi) or if there is a unit of flow on the edge (uj‘, vi).
[20] Balloon Distribution and Subcontractor Constraints
(a) Define a flow network as follows. There is a source s, a node xi representing each balloon i, a node zi representing each condition ci, and a sink t. There are edges (s, xi) of capacity 2, (xi, zj) of capacity 1 whenever cj E Si, and edges (zj, t) of capacity k. We then test whether the maximum s-t flow has value nk. The Ford-Fulkerson algorithm to find a maximum flow has running time O(|E|C), where E is the number of edges and C is the total capacity of edges out of s. Here we have |E|=O(mn) and C=2m, so the running time is O(m2n). An alternate but related solution would place a lower bound of k on each edge of the form (zj, t). One would then place a demand of —nk on s and nk on t, and test whether there is a feasible circulation.
(b) Break all edges (xi, zj). Insert new nodes ypj for each sub-contractor p and condition cj. Add an edge (xi, ypj) of capacity 1 when cj E Si and balloon i is produced by sub-contractor p. Add an edge (ypj, cj) of capacity k — 1. Again, test whether the maximum s-t flow has value nk. As in part (a), the running time is O(|E|C). Here E is still O(mn), and C=2m, so the running time is O(m2n). The alternate solution in (a) based on circulations with lower bounds can be modified in the same way.
[21] Mobile Device Connectivity Testing
(a) Let n>=3. Suppose the first laptop is within range of all access points, and all laptops are within range of the first access point, but these are all the possible connections. Then we need to connect the first laptop to all but the first access point, and all but the first laptop to the first access point, for a total of 2n — 2 > n connections.
(b) We build the following flow network. There is a node vi for each laptop i, a node wj for each access point j, and an edge (vi, wj) of capacity 1 if laptop i is within range of access point j. We then connect a super-source s to each of the laptop nodes by an edge of lower bound 1 and capacity upper bound n, and we connect each of the access point nodes to a super-sink t by an edge of lower bound 1 and capacity upper bound n. We give a demand of —k to the source s and a demand of +k to the sink t. We claim that there is a test set of size k if and only if there is a feasible circulation in this network. If there is a test set of size, then we send one unit of flow from s to t along each of the paths s,vi,wj,t, where laptop i is connected to access point j. This satisfies all lower and upper bounds on capacities, and it satisfies the demand of k. Conversely, if there is a feasible circulation, then there is one with integer values. We connect laptop i to access point j if the edge (vi, wj) carries one unit of flow, and we observe that the lower bounds on capacities ensure that this is a test set. The running is the time required to solve a circulation problem on a graph with O(n) nodes and O(n2) edges.
[22] Rearrangeable Matrices and Bipartite Matching
(a) Let n>=3, define all entries in the first row and column to be 1, and define all other entries to be 0. This matrix is not rearrangeable: essentially, the first column can provide one diagonal entry equal to 1, and the first row can provide another, but that’s all, and we have n>=3.
(b) Define a bipartite graph G with nodes x1,..,xn on the left and nodes y1,..,yn on the right. We include an edge (xi, yj) for each pair (i, j) such that entry mij =1. We claim that M is rearrangeable if and only if G has a perfect matching. To prove this first suppose that G has a perfect matching in which xi is matched to yf(i). Then we swap rows so that row i ends up in row f(i); note that this is well-defined since f is a bijection of {1,2,..,n} to {1,2,..,n}. Since mi,f(i)=1 for all i, the resulting rearranged matrix has all diagonal entries equal to 1. Conversely, suppose that M is rearrangeable, and suppose that after swapping, row i has moved to f(i), and column j has moved to g(j). Since f and g are both bijections of {1,2,..,n} to {1,2,..,n}, we can consider f-1(k) and g-1(k) for each k. Note that (xf-1(k), yg-1(k) is an edge of G for each k, since after swapping, the (k, k) entry is equal to 1, and this set of edges forms a perfect matching in G.
[23] Upstream, Downstream, and Central Nodes in a Flow Network
Consider the cut (A*, B*) found by performing breadth-first search on the residual graph Gf at the end of any maximum flow algorithm. We claim that a node v is upstream if and only if v E 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 E A* were not upstream. Then there would be a minimum cut (A’, B’) with v E B’. Now since v E A*,
there is a path P in Gf from s to v. Since v E B’, this path must have an edge (u, w) with u E A’ and w’ E 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 nodes that can reach t in Gf, and let A** = V — B**. Then (A**, B**) is a minimum cut, and a node w is downstream if and only if w E B**. Thus, our algorithm is to compute a maximum flow f, build Gf, and use breadth-first search to find the sets A* and B**. These are the upstream and downstream nodes respectively; the remaining nodes are central.
[24] Construct a graph G=(V,E) where the nodes represent people that are either owed or owe money. Let there be an edge (u,v) if person u owes person v money and let the cost of this edge be the amount of money owed. Note that if (u,v) exists, then (v,u) does not exist since we may just adjust for the difference. Let G’ be the undirected graph obtained from G by ignoring the directions of the edges. We repeatedly run BFS on G’ to find undirected cycles and eliminate them as specified below. We do this as follows:
Search for an undirected CYCLE
While CYCLE != NULL (a cycle exists)
Find the edge in CYCLE with minimum cost.
Let this minimum cost be stored in MINCOST and the corresponding edge in MINEDGE.
For each edge EDGE in CYCLE
If EDGE has the same direction as MINEDGE, reset EDGE’s cost to its current cost less MINCOST
Else reset EDGE’s cost to its current cost plus MINCOST Endif
Endfor
Remove all edges whose cost has been reduced to 0 (including MINEDGE)
Search for a new undirected CYCLE
Endwhile
Note that each time through the while loop, we get rid of at least one edge. Since there are m edges, we go through the outer loop at most m times. Also finding a cycle via BFS takes 0(m+n) time. Thus the overall running time is O(m(m+n)). In each iteration, we preserve all imbalances; so at the end we will have a reconciliation. Further, we preserve the direction of the edges since we modify according to the direction and only by the minimum cost edge in the cycle; thus, at the end, we will have a consistent reconciliation. Since G’ has no cycles at termination, it must be a tree or a forest, and therefore has at most n — 1 edges. Thus we have produced consistent reconciliation in which at most n—1 checks get written. Note: Observe that it is necessary to search for undirected cycles in G, rather than directed cycles, since eliminating only the directed cycles in G willnot necessarily reduce the number of edges to n — 1.
[25] We first decide whether the phones can be fully connected in the starting position of p1. To do this, we construct a bipartite graph G=(XUY,E), where X is the set of phones, Y is the set of base stations, and there is an edge (pi, bj) if and only if the distance from pi to bj is at most DELTA. By the definition of G, a perfect matching corresponds to a legal assignment of phones to base stations; thus, the phones can be fully connected if and only if G has a perfect matching, and this can be checked in 0(n3) time. Define an event to be a position t on the path of phone p1 at which it first comes into range of a base station, or first goes out of range of a base station. The path of p1 is a line, and the set of points in range of a base station bj is a circle of radius delta; since the line can intersect the circle at most twice, there is at most one event in which p1comes into range of bj and at most one event in which it goes out of range of bj. Thus, there are at most 2n events total; we can sort them by x-coordinate in the order t1,t2,..,tk, with k=2n.>=2n,>
[26] (a, b) We define a graph G = (V, E) with source s, vertices vi,..,vd for each day, vertices w1,..,wk for each person, and sink t. There is an edge of capacity 1 from s to each vi, an edge of capacity 1 from vi to each wj with pj E Si, and an edge of capacity /*UPPERBOUND*/ [DELTAj] from wj to t. We know there is a feasible fractional flow in this graph of value d, obtained by assigning a flow of value of 1/|Si| to each edge (vi wj), and flow values to all other edges as implied by the conservation condition. Thus there is a feasible integer flow, and the flow values on the edges of the form (vi, wj) define a fair driving schedule in the following way: pi drives on day i if and only if f(vi,wj)=1. This also gives a polynomial-time algorithm to compute the schedule.
[27] (a) Build the following flow network. Create a node ui for each TA i, and a node vj for each time slot Ij, with an edge (ui, vj) of capacity 1 whenever i is available for time slot j. Attach a source s with edges (s, ui) of lower bound a and capacity b. Attach a sink t with edges (vj, t) of capacity 1. Finally give s a demand of —c and t a demand of c. We claim there is a feasible circulation iff there is an office hour assignment. If there is an office hour assignment, we can send a unit of flow s-ui-vj-t for each office hour that is held, and this meets all capacities, lower bounds, and demands. Conversely, if there is a circulation then there is an integer-valued one and each edge (ui, vj) carrying a unit of flow will specify an assignment of a TA to a time slot. Comment: It was necessary to assign demands to s and t and then look for a circulation, rather than to simply say “Find a maximum flow from s to t.” The point is that we don’t have an algorithm (either from class or the book) that finds a maximum flow in the presence of lower bounds on the edges; once we have lower bounds in addition to capacities, we only have an algorithm that can test for a feasible circulation with demands, and so one needs to set things up that way. (b) We take the construction from (a) and delete the edges (vj, t). Instead we create a node xl for day l; we add an edge (vj, xl) of capacity 1 when time slot Ij falls on day l, and we create an edge (xl, t) of lower bound dl and capacity c for each day l. Finally, we again look for a feasible circulation.
=k,>