King A has problems to administer his realm. His court contains n knights and he rules over m counties. The knights differ in their abilities and local popularity: Each knight i can oversee at most q_i counties, and each county j will revolt unless it is overseen by some knight in a given subset S_j {1, . . . , n} of the knights. Only 1 knight can oversee a county, to prevent conflicts between the knights.The king discusses the problem with his court magician G.

Show how G can use the Max-Flow algorithm to efficiently compute an assignment of the counties to the knights that prevents a revolt, provided that one exists. How can he determine whether the algorithm was successful? Prove the complexity of this algorithm, in terms of some function F(v, e), where F(v, e) denotes the running time of a Max-Flow algorithm on a graph with v vertices and e edges.

Suppose that G runs the algorithm from above, but it does not produce a solution that fits the constraints and prevents all counties from revolting. King A demands a explanation. While he believes that the algorithm (and proof) is correct, he doubts that G has executed the algorithm correctly on the large given instance. G needs to convince the king that no suitable assignment is possible under the given constraints. How can G prove this, based on the structure of the Max-Flow problem? (Note that the argument must work for every instance where there is no solution, not just a particular instance.)