CompSci 163/265, Spring 2015, Homework 4

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

    (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).