# CompSci 163/265, Spring 2015, Homework 4

1. Draw the flow network representing a baseball elimination problem in which

• We wish to know whether the Angels have been eliminated from the American League West; the other teams in the division are the Astros, A's, Mariners, and Rangers.
• There are six games left for the other teams to play, one for each pair of teams.
• If they win all their remaining games, the Angels can afford to let the Astros win at most two games, the Mariners win at most three games, and the A's and Rangers win at most one game.

(You do not need to find the maximum flow for your network; just show its vertices, edges, and edge capacities.)

2. In the solution to a maximum flow problem, is it always true (for every possible network and every possible maximum flow on that network) that the subset of the edges that have nonzero flow amounts forms a directed acyclic graph? Explain why or find a counterexample.

3. For both of the following parts, you may use the fact that an $n$-vertex directed graph (without multiple edges between the same two vertices) has $O(n^2)$ edges.

1. Prove that, for some $n$-vertex inputs to the maximum flow problem, every augmenting path algorithm can be forced to use a number of augmenting paths that is proportional to $n^2$.

2. (265 only): Prove that, for every $n$-vertex input to the maximum flow problem, there exists a sequence of augmenting paths with only $O(n^2)$ paths. (Hint: find the maximum flow first and use it to guide your choice of paths. Try to find paths that eliminate at least one edge from the remaining flow.)

4. Suppose we are holding a preference ballot with three candidates: Washington, Jefferson, and Hamilton. Each voter can choose one of the six permutations of those candidates, describing which one is their favorite, second favorite, and least favorite. There are 100 voters. Choose how many voters should vote for each of the six permutations, in such a way that that Washington is the Condorcet winner (he would win each one-on-one pairing of two candidates that he participates in) but gets the smallest number of first-place votes (so he would be eliminated first in an instant-runoff election).