Computing a Maximal Matching

Computing a Maximal Matching


Maximal matchings are a useful tool for
getting a coarsened graph. All we need now is
an algorithm to compute one. Let me describe a simple scheme
to you based on randomization. At each step of this scheme, you’ll
choose any unmatched vertex at random. So initially, no edges are matched,
so let’s pick any vertex. How about this one? Next, you’ll match this vertex to
one of it’s unmatched neighbors. Again, since we’re just starting,
all of the neighbors are unmatched. So how do we pick one? Well, there are lots of strategies. For example,
you could just pick one at random. A different approach is something
called a heavy edge matching strategy. So heavy. So heavy. The idea is to look at the unmatched
edge with the highest weight and then choose it. For instance,
suppose these are the edge weights. Then among the two unmatched neighbors,
this edge has the higher edge weight, two versus one. So you’d choose it. But why is the heavy edge
matching strategy a good one? In fact, there’s not a whole lot of
definitive rigorous analysis out there. But there is a lot of
experimental evidence. What I want to do now is just
give you some informal intuition. Consider some graph Gi. Suppose we were to
match these two edges. Contracting them would
yield a course in graph. Let’s call it Gi + 1. Note the edge weight of two that
connects the two super vertices. Now, if you were to sum the edge weights
in the original graph, you’d get 12. That’s because there are 12
edges each of unit weight. Here let me use the notation X of some object to count the number
of edges in that object. Now the sum of the weights
on the final graph is 10. This is just the total edge weight of
the original graph minus the edge weight of the matched edges. Here, let Mi denote the matching. Now, the strategy of
selecting heavy edges will tend to try to increase this factor. And if this factor is bigger,
then this factor will be smaller. In other words, the heavy edge
heuristic is really about increasing this term in order to decrease the
overall edge weight in the next graph. The heuristic idea is that
the smaller this term is, the more likely it is that all
the edges you’ll cut will be small. Again, this is clearly
not a rigorous proof. In fact,
there are a ton of other heuristics. But most of the evidence is empirical. Anyway, if this is a topic of interest
to you, head to the instructors notes or the class forum for pointers to papers that will discuss
all these issues in a lot of detail.

One thought to “Computing a Maximal Matching”

Leave a Reply

Your email address will not be published. Required fields are marked *