$($b$)$ King Arthur 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$sube$\{1,$dots,$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 Merlin.

i$.$ Show how Merlin 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.

ii$.$ Suppose that Merlin runs the algorithm from above, but it does not

produce a solution that fits the constraints and prevents all counties

from revolting.

King Arthur demands an explanation. While he believes that the al$-$

gorithm $($and proof$)$ is correct, he doubts that Merlin has executed the

algorithm correctly on the given large instance. Merlin needs to con$-$

vince the king that no suitable assignment is possible under the given

constraints. Re$-$running the algorithm step$-$by$-$step in front of the king

is not an option, because the king does not have that much time.

How can Merlin quickly convince the king that there is no solution, 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.$)$