CS 163/265, Winter 2025, Practice Problem Set 9

1. The cube graph is a bipartite graph with eight vertices, representing the eight corners of a cube, and twelve edges connecting pairs of adjacent corners. Draw a flow network whose integer maximum flows represent the maximum matchings of the cube graph.

2. We saw in the lecture that $M+I=n$ for $n$-vertex bipartite graphs with maximum matching size $M$ and independent set size $I$. For which pairs of numbers $M$ and $I$ is it possible to find a bipartite graphs with maximum matching size $M$ and independent set size $I$? Describe a method of constructing these graphs for all pairs of numbers $M$ and $I$ for which it is possible, and explain why it is not possible for any other pair. (Hints: the two sides of the bipartition are independent sets. The graphs you construct do not need to be connected.)

3. For a maximum-weight matching problem in a complete bipartite graph, with positive edge weights, the greedy algorithm repeatedly matches the pair of unmatched vertices that have the heaviest edge. Each pair is matched permanently rather than allowing the matching to change as the algorithm progresses. Unlike the Hungarian algorithm, the greedy algorithm does not always find optimal matching.

   1. Find positive weights on a four-vertex cycle graph for which the total weight found by the greedy algorithm is only $\frac{1}{2}+\epsilon$ times the total weight of the maximum-weight matching, for an arbitrary parameter $\epsilon >0$. (It may simplify your calculations to adjust the weights so that the optimal matching has total weight 1.)

   2. Argue that the greedy algorithm always finds a matching whose weight is at least half the optimal weight. That is, its approximation ratio is $\frac{1}{2}$. (Hint: each edge of the optimal matching must either be part of the greedy matching, or be overlapped by a heavier edge of the greedy matching. How many optimal edges can a greedy edge overlap?)

4. Consider a stable matching instance with eight participants, ABCD on one side of the bipartition and WXYZ on the other. The preference orderings are A:ZWXY, B:WXYZ, C:ZYWX, D:WZXY, W:BACD, X:CBAD, Y:BCAD, Z:CDAB. That is, A's first choice is Z, then W, etc.

   1. There is a matching where each participant gets their second choice, but it is not stable. Find an unstable pair for it.

   2. Assign one point for a first choice match, two for a second choice match, etc., so that for instance the matching where each participant gets their second choice has 16 points total. For this stable matching instance, does there exist a stable matching that is also a minimum-weight matching for these numbers of points? Why or why not? (Hint: In a stable matching, pairs that are each other's first-place choice must be matched to each other.)