Notes:

• For this class is is generally not necessary to validate input in your pseudocode: if a problem says the input will be in a certain form then write your pseudocode under the assumption that the input is in that form.
• "Find/devise/give an efficient algorithm" means "find an algorithm that is as efficient as possible, and you have to figure out for yourself whether your solution can be improved."

Problem : Suppose that to build a single electric car we need a three-person team consisting of a machinist, a welder, and an electrician. We have a pool of $k$ machinists, $m$ welders, and $n$ electricians. Each tradesperson can be assigned to at most one team. Some pairs of machinists and welders refuse to work together, and some pairs of welders and electricians refuse to work together (the machinists and electricians do not work on the cars at the same time, so their personal squabbles are irrelevant). Describe a polynomial-time algorithm to determine the maximum number of teams we can form given the constraints on who will work with whom and prove that it is correct (hint: if you can solve the problem by creating an appropriate input to a standard algorithm then you need only prove that input correctly models the problem). Explain why the running time of your algorithm is polynomial in $k$, $n$, and $m$.

Problem : Consider the problem of computing the maximum flow in a graph with integer capacities where there are edges $(u, v)$ and $(v, u)$ between every pair of vertices (with $c(u, s) = 0$ and $c(t, v) = 0$ for all $u$ and $v$ and possibly with $c(u, v) = 0$ and/or $c(v, u) = 0$ for other pairs of vertices as well). Show how to update the augment procedure in the Ford-Fulkerson method in such a way that the following invariant is maintained:

• $f$ is an integer-valued flow
• $f(u, v) = 0$ or $f(v, u) = 0$ for every pair of vertices $u$ and $v$ (so there is flow in at most one direction between any two vertices)
• $c_r(u, v) = c(u, v) - f(u, v)$ whenever $f(u, v) > 0$
• $c_r(u, v) = c(u, v) + f(v, u)$ whenever $f(u, v) = 0$

Write the updates that happen in the loop in augment for both the flow $f$ and the residual capacities $c_r$.

Problem : Tardos and Kleinberg, Ch. 7, Ex. 11. Be sure to include

• an explanation of what the maximum flow in your graph is;
• the sequence of paths that leads to non-optimal flow;
• an explanation of why there are no more paths of positive residual capacity after that sequence of paths when you omit backward edges from the residual graph; and
• an explanation of how to generalize the above so that you end up with an arbitrarily small ratio of found flow to maximum flow.