Maximal Friends

Achieving a factor of two of the optimal seems to happen often in computational problems. As in the Traveling Salesman Problem, this problem uses a setting involving roads, but with a strong xenophobic bite.

Imagine a set of city-states. There are roads connecting some of them and it’s possible to travel from any city to any other, though the trip may require some intermediate stops. There may be several routes between two cities, i.e., the roads need not constitute a spanning tree. All roads are two-way.

We say two cities are neighbors if there is a road connecting them. Cities make alliances only with neighbors. Further, no city makes more than one alliance. If cities A and B are allied, we will call them matched. A maximal matching occurs when every city C is either matched or all neighbors of C are matched with other cities.

Warm-Up

Suppose there are eight cities. How few matches could there be in a maximal matching?

Solution to Warm-Up

There could be just one, represented here by the solid line segment in Figure 2-26.

Figure 2-26: Each line segment (dashed or solid) represents a road. The solid line represents an alliance. Only C4 and C5 are matched. No other city has an ally.

That single matching precludes all others and therefore is maximal. At this point, let me remind you of the difference between maximal and maximum: a maximal state is one to which you can add nothing, in this case more matchings. Maximum means you cannot get a larger number. So this matching is maximal, but it doesn’t give the maximum number of possible matches of any maximal matching. That honor belongs to the matching in Figure 2-27 (among many other symmetrically constructed ones).

Figure 2-27: In this case, we have two matchings: C3 with C4, and C5 with C7. Other pairs of cities could be matched, but there cannot be more than two matching pairs in all.

The warm-up shows that the poor maximal matching of the first figure had half the number of matches as the one in the second figure. One might wonder how general an observation that is.

1. Is there any configuration of cities and roads for which the maximum maximal matching has more than twice as many matches as some other maximal matching? If so, show it. Otherwise, prove that this cannot happen.

Solution to Maximal Friends

1. Is there any configuration of cities and roads for which the maximum maximal matching has more than twice as many matches as some other maximal matching? If so, show it. Otherwise, prove that this cannot happen.

It cannot happen. That is, the maximum maximal matching (let’s call it Mmax) cannot have more than twice the number of matches than even the worst maximal matching (let’s call that one Mbad). The reason is simple. Consider an edge in Mbad between nodes n1 and n2. Eliminating that edge makes n1 and n2 available to match other nodes, but n1 can match only one other node and similarly for n2. So eliminating the edge between n1 and n2 can do no more than make two other edges possible.