CS 163 / CS 265 Homework 7, due Friday, March 1

1. In the lecture we saw an input to the stable marriage algorithm with five men and five women in which all the women ended up married to their first choices. Find a different input (again, with five men and five women) in which the same algorithm marries all the women to their last choices.

2. Among the graphs of the regular polyhedra (the tetrahedron, cube, octahedron, icosahedron, and dodecahedron) which ones are bipartite? Describe a two-color coloring of the ones that are bipartite, and describe an odd cycle in the ones that are not bipartite.

3. In class we showed how to transform a bipartite graph into a flow network such that an integer maximum flow can be used to find a maximum matching in the original graph. Describe how a minimum cut in the same flow network can be used to find a maximum independent set in the original bipartite graph.

4* (265 only). The non-crossing stable marriage problem is a variation of the stable marriage problem in which n men and n women are placed around a circle, alternating between men and women, in a fixed and preset order. The goal is to find a stable marriage with the property that, if you draw line segments connecting the two positions on the circle for each couple, then no two of these line segments would cross each other. For instance, if the order of three men and three women around the circle is Alice--Bob--Carol--Daniel--Eve--Frank, then it would not be allowed to match Alice to Daniel and Bob to Eve, because those two couples determine line segments that cross each other. However, an unmarried couple who like each other better than their partners is only considered unstable if their line segment does not cross one of the line segments between married couples. For instance, in the same example, if Alice is married to Daniel, then Bob and Eve cannot form an unstable couple, even if they prefer each other to their partners Carol and Frank.

(a) Show that, for three men and three women, the non-crossing stable marriage problem always has a solution.

(b) For larger (equal) numbers of men and women, does the non-crossing stable marriage problem always have a solution? If so, prove it; if not, find a counterexample.