Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 577

Assignment 9 – Network Flow

Fall 2022

2.  Kleinberg, Jon. Algorithm Design (p . 418, q.  8) Consider this problem faced by a hospital that is trying to evaluate whether its blood supply is sufficient:

In a (simplified) model, the patients each have blood of one of four types: A, B, AB, or O. Blood type A has the A antigen, type B has the B antigen, AB has both, and O has neither.  Patients with blood type A can receive either A or O blood.  Likewise patients with type B can receive either B or O type blood. Patients with type O can only receive type O blood, and patients with type AB can receive any of the four types.

(a)  Let sO ,sA ,sB ,sAB  denote the hospital’s blood supply on hand, and let dA ,dB ,dO ,dAB  denote their projected demand for the coming week. Give a polynomial time algorithm to evaluate whether the blood supply is enough to cover the projected need.

(c)  Network flow is one of the most powerful and versatile tools in the algorithms toolbox, but it can be difficult to explain to people who don’t know algorithms. Consider the following instance. Show that the supply is insufficient in this case, and provide an explanation for this fact that would be understandable to a non-computer scientist.  (For example: to a hospital administrator.)  Your explanation should not involve the words flow, cut, or graph.

blood type    supply    demand  

O                   50           45

A                   36           42

B                   11           8

AB                8             3

3.  Kleinberg, Jon.  Algorithm Design (p .  419, q.  10) Suppose you are given a directed graph G = (V,E). This graph has a positive integer capacity ce  on each edge, a source s ∈ V , a sink t ∈ V . You are also given a maximum s − t flow through G:  f . You know that this flow is acyclic (no cycles with positive flow all the way around the cycle), and every flow fe  ∈ f has an integer value.

Now suppose we pick an edge e*  and reduce its capacity by 1 unit.  Show how to find a maximum flow in the resulting graph G*  in time O(m + n), where n = |V | and m = |E|.

4.Kleinberg, Jon. Algorithm Design (p . 420, q.  11) A friend of yours has written a very fast piece of code to calculate the maximum flow based on repeatedly finding augmenting paths. However, you realize that it’s not always finding the maximum flow. Your friend never wrote the part of the algorithm that uses backward edges! So their program finds only augmenting paths that include all forward edges, and halts when no more such augmenting paths remain.  (Note:  We haven’t specified how the algorithm selects forward-only augmenting paths.)

When confronted, your friend claims that their algorithm may not produce the maximum flow every time, but it is guaranteed to produce flow which is within a factor of b of maximum.  That is, there is some constant b such that no matter what input you come up with, their algorithm will produce flow at

least 1/b times the maximum possible on that input.

Is your friend right? Provide a proof supporting your choice.

5. Implement the Ford-Fulkerson method for finding maximum flow in graphs with only integer edge ca- pacities, in either C, C++, C#, Java, or Python. Be efficient and implement it in O(mF) time, where m is the number of edges in the graph and F is the value of the maximum flow in the graph. We suggest using BFS or DFS to find augmenting paths.  (You may be able to do better than this.)

The input will start with a positive integer, giving the number of instances that follow. For each instance, there will be two positive integers, indicating the number of nodes n = |V | in the graph and the number of edges |E| in the graph.  Following this, there will be |E| additional lines describing the edges.  Each edge line consists of a number indicating the source node, a number indicating the destination node, and a capacity. The nodes are not listed separately, but are numbered {1 . . . n}.

Your program should compute the maximum flow value from node 1 to node n in each given graph. A sample input is the following:

2

3  2

2  3  4

1  2  5

6  9

1  2  9

1  3  4

2  4  1

2  5  6

3  4  4

3  5  5

4  6  8

5  6  5

5  6  3

The sample input has two instances. For each instance, your program should output the maximum flow on a separate line.  Each output line should be terminated by a newline.  The correct output for the sample input would be:

4

11