Chapter 25: Matchings in Bipartite Graphs: Stable Marriage and the Hungarian Algorithm

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Welcome back everyone to the Deep Dive.

Today we are diving into a topic that on the surface might sound kind of theoretical, but trust me, it's way more relevant than you might think.

We're talking about matching, specifically in graphs.

Ah yes, matchings.

You can think about it like pairing things up, making connections where there's no overlap.

Exactly, like assigning tasks to people, you know, making sure everyone has a job and no one's doing the same thing.

Or even think about like matching organ donors with recipients, that kind of thing.

Yeah, perfect examples.

And while matchings can pop up in all sorts of networks, we're going to zoom in on a specific type of graph called bipartite graphs for this

Now I remember bipartite graphs from our graph theory, Deep Dive.

That's where you have two distinct groups, right?

Exactly, you got it.

Two separate sets of vertices and the connections or edges only exist between the groups, not within them.

So like imagine one group is job seekers and the other is open positions.

The connections show who's qualified for which job.

Spot on.

And this kind of structure, this bipartite setup, it's super useful for modeling all sorts of and that's what makes it so powerful.

So for today's Deep Dive, we're going to tackle three main challenges within this world of bipartite matching.

Okay, I'm ready.

Lame on me.

First up is finding the biggest possible matching, you know, the maximum number of pairings you can make.

That's the maximum bipartite matching problem.

Right, so squeezing in as many connections as we can.

Makes sense.

Then we'll move on to situations where it's not just about quantity, but also about how do we make pairings that are stable, where no one's going to want to switch things up.

And that's the stable marriage problem.

Ah, so like matching couples or even residents to hospitals where everyone's got their own wish list.

Exactly.

And finally, we'll look at cases where those connections, those edges in our graph, actually have different values, different weights attached to them.

And we want to find the matching that gives us the best possible overall result.

So like maximizing profit or efficiency, something along those lines.

Precisely.

And that's where the Hungarian algorithm for the assignment problem comes in.

It helps us figure out the best way to allocate resources or make those assignments.

Okay, sounds like we've got a lot to cover.

Let's dive into this maximum matching thing first.

How do we actually go about finding the biggest possible matching?

Yeah, where do we even begin?

Well, first we got to get a couple of key terms straight.

We say a vertex, that's like a point in our graph, is matched if it's part of a pair.

It's connected by an edge in our matching, right?

And if it's not connected, it's unmatched.

Makes sense.

So matched is paired up, unmatched is solo.

Exactly.

Now you might stumble upon what's called a maximal matching.

This means you can't just add any more edges to it without breaking the rules of a matching, you know, without having overlaps.

Okay, so it's like you filled up all the we really want is a maximum matching.

That's the matching with the absolute most pairs possible.

So that's our goal, maximum matching, the most connections we can make.

Precisely.

And to get there, we got to talk about these things called M alternating paths and M augmenting paths.

Now I know those names might sound a bit intimidating, but bear with me, the idea is actually pretty neat.

Okay, I'm all ears.

Let's hear about these paths.

So picture this.

An M alternating path is like taking a walk through the graph where you're hopping between edges that are in our current matching, we'll call it the set of edges, M, and edges that aren't in M, you're going back and forth in and out of the matching.

Okay, like a zigzag pattern through the connections.

Exactly.

Now an M augmenting path is a special kind of M alternating path.

It's a path that starts and ends at unmatched vertices, so it connects to lonely souls, so to speak.

So it's an alternating path that bridges the gap between two connected points.

Exactly.

And here's where things get really interesting.

Lemma 25 .1 comes in and tells us if we find one of these M augmenting paths, we can actually make our matching bigger.

Really?

How do we do that?

Right?

It's like a clever little trick.

We basically flip the edges along that path.

So the edges that were in the matching are now out and the ones that weren't are now in.

Interesting.

So by flipping the status of those connections along the path, we change the overall matching.

Yeah.

And the best part is this flip, it always adds one more edge to our matching.

So we're essentially connecting those two unmatched vertices that the path started and ended at.

You got it.

It's like we're rearranging existing pairings to accommodate two more people.

And then Corollary 25 .2 takes this even further.

It says if you've got multiple M augmenting paths that don't overlap, you can do this flipping trick on all of them at the same time.

So you can get multiple new connections in one go.

Boom.

Exactly.

So basically the takeaway is that by cleverly finding and flipping these augmenting paths, we can keep growing our matching until we can't find any more of them.

That makes sense.

It's like we're strategically rearranging the connections to create more pairs.

So it sounds like finding these M augmenting paths is crucial.

Absolutely.

They're the key to maximizing our matching.

And Lemma 25 .3 gives us another way to think about this.

Imagine you have two different matchings in the same bipartite graph.

Okay.

Two different ways of pairing things up.

Right.

Now, if you look at the edges that are in one matching, but not the other and vice versa, they'll form a bunch of alternating paths and cycles.

So it's like highlighting the differences between the two matchings where they agree and disagree.

Yeah, precisely.

Now, if one of these matchings is bigger than the other, those differences, those alternating paths, they have to include at least one augmenting path.

It's kind of like the more potential there is to grow your matching, the more of these growth paths you'll find when you compare it to a smaller one.

That's interesting.

So the bigger the difference in size between the matchings, the more opportunities there are to improve the smaller one.

Exactly.

So we're looking for these augmenting paths, flipping edges and making our matching bigger and bigger.

But how do we know when we've hit the jackpot?

How do we know we found the maximum matching?

Yeah.

When do we stop this flipping business?

Well, corollary 25 .4 comes to the rescue here.

It basically says that a matching is a maximum matching if and only if there are no more M augmenting paths left in the graph.

So if we can't find a path that starts and ends in an unmatched vertex, we're done.

We've reached the maximum.

You nailed it.

There's simply no way to squeeze in any more connections.

We've reached peak matching.

Okay.

That makes sense.

So the whole problem boils down to finding these augmenting paths efficiently.

Right.

Exactly.

And that's where the Hopcroft -Karp algorithm struts onto the scene.

Okay.

Tell me about this Hopcroft -Karp algorithm.

It's a really clever algorithm that was specifically designed for finding a maximum matching in a bipartite graph.

And when we talk about efficiency, it boasts a time complexity of are you ready for this OVE?

Okay.

You lost me a bit with the O notation.

Right.

It's a bit of computer science jargon.

Basically, it means the algorithm is pretty darn fast, especially when you have a large number of items and potential connections.

The number of steps it takes to find that best matching, it grows relatively slowly compared to the size of the problem itself.

So the more complex the problem, the better this algorithm performs compared to others.

You could say that.

Yeah.

It's well suited for tackling those larger matching challenges.

Okay.

That sounds impressive.

But how does this Hopcroft -Karp algorithm actually work?

What are the steps involved?

So the algorithm works in these rounds or iterations, and each iteration has three main phases.

Three phases.

All right.

First, it sets up a directed graph.

We call it GM.

This is based on our current matching.

The direction of the edges in this graph basically tells us whether an edge is part of the matching or not.

It's like creating a one -way map of our current pairings and potential connections.

Got it.

So we've got our map.

What's next?

Now in phase two, we use this thing called search or BFS to build another directed graph.

This one called H.

Okay.

Another graph.

What's special about this one?

This graph is all about finding the shortest augmenting paths in that first graph, GM.

We want the most direct routes to increase our matching, no scenic detours.

So we're looking for the quickest way to connect those unmatched vertices.

Exactly.

Efficiency is key.

And then comes the final phase, phase three.

Here we use depth first search or DFS on what's called the transpose of H.

Don't worry too much about the technical details there.

What matters is that this step helps us find a maximal set of those shortest augmenting paths.

Maximal meaning?

It means we find as many of their shortest paths as possible without any of them overlapping.

And remember, from corollary 25 .2, we can flip all those paths at once.

So it's like we're identifying a whole bunch of opportunities to grow our matching and then acting on all of them simultaneously.

A bulk matching operation.

Boom.

Exactly.

Way more efficient than going one by one.

Now I won't bore you with all the math, but the chapter goes through a whole bunch of lemmas 25 .5, 25 .6, 25 .7 that prove why this whole thing works.

And then there's theorem 25 .8, the grand finale.

It formally proves that this Hopcroft -Krack algorithm actually finds the maximum matching and that it does it with that awesome OV time complexity.

So you can rest assured this thing's got solid mathematical back.

Okay.

That's good to know.

So that's how we tackle maximum matching.

But what about those cases where it's not just about quantity, but also about making sure everyone's happy with their match.

Ah, you're talking about the stable marriage problem.

Let's dive into that one.

Right.

So it's like, imagine we're not just assigning tasks, but trying to match people up, maybe for dating or assigning residents to hospitals.

They've got their preferences, who they want to be with or where they want to work.

A simple maximum matching might give us a lot of pairs, but some of those pairs might be kind of unhappy with the situation.

Exactly.

In matching lingo, we call that an unstable matching.

It happens when there's what we call a blocking pair.

Blocking pair.

What's that?

It's when you have two people, let's say person A and person B, they're not matched right now, but they would both prefer each other over they're currently with or over being alone.

I see.

So it's like they're both looking at each other thinking, hey, we'd be better off together.

Exactly.

And that's a problem because it makes the whole matching unstable.

Those two have a strong incentive to ditch their current matches and get together, which would just mess things up for everyone.

Right.

It's like a recipe for drama.

So how do we find a matching where no one has that temptation, where everyone's relatively content?

Well, that's where the Gale -Shapley algorithm comes in.

Specifically, we'll focus on what's called the woman -oriented version.

Woman -oriented, huh?

Interesting.

Yeah.

It's a classic algorithm that guarantees we'll find a stable matching.

And it works in these rounds.

In each round, every woman who's not currently matched proposes to the man highest up on her preference list who she hasn't proposed to yet.

Okay.

So it's like the women are taking the initiative here.

Exactly.

They're putting themselves out there.

Now, the men on the receiving end of these proposals, they've got to consider all their options.

If a guy's not currently matched, he'll just say yes to his favorite woman among those who proposed to him.

But if he's already engaged, he's got to compare the new proposals to his current fiance and see who he likes better.

If he prefers one of the new proposals, he'll break off his engagement and accept the proposal from his new favorite, leaving his old fiance unmatched.

Oh, so it's not just about who proposes first, but also about who each man pursues among all the options he has.

Exactly.

It's a whole game of proposals and engagements until finally everyone's matched up.

Sounds like a pretty structured system.

But does this algorithm always lead to a stable matching?

And does it even finish?

Like, what if it just keeps going forever?

That's where Theorem 25 .9 steps in to reassure us.

It proves that this algorithm always wraps up after a certain number of rounds.

And more importantly, it always produces a stable matching.

No blocking pairs, no drama.

That's great.

A guaranteed happy ending.

So this Gale Shapley algorithm, is it efficient?

Yeah, it's pretty decent in terms of efficiency.

Its time complexity is o n, where n is the number of individuals on each side.

Basically, it means it's pretty quick for problems of a reasonable size.

Okay, so we can find those stable matches without it taking forever.

Exactly.

Now, there's a fascinating quirk to this algorithm, and it might be a bit counterintuitive.

Okay, I'm intrigued.

Tell me more.

So Theorem 25 .111m states that the stable matching we get from this woman -oriented version is always the same.

It doesn't matter the order the women propose, the final result is fixed.

And here's the kicker.

This matching is the best possible outcome for the women.

Each woman ends up with the most desirable partner she could possibly get in any stable matching.

Wow, that's pretty powerful.

So just by having the women propose, they're ensuring they get the best stable outcome for themselves.

Exactly.

Now you might be wondering, what about the men?

Yeah, where do they stand in all of this?

Well, Corollary 25 .13 tells us that the same matching is actually the worst possible stable outcome for the men.

Each man ends up with the least preferable partner he could have in any stable matching.

Wow, that's quite an imbalance.

So if we flip things around and let the men propose, they get the best stable outcome, and the women would get the worst.

Precisely.

It's a fascinating asymmetry that shows how the design of these algorithms can have a real impact on the different groups involved.

It's not just about finding a stable solution, but also about considering who might be benefiting more from that stability.

That's a really important point, especially if you're thinking about using these algorithms in real -world applications.

You've got to be mindful of whose preferences are being prioritized.

Absolutely.

Now, ready to move on to our final challenge.

What happens when those connections, those edges actually have values or weights assigned to them?

Okay, so now we're talking about maximizing not just the number of pairs or their happiness, but the overall value of the matching itself.

This is the assignment problem, right?

You got it.

Think of it like assigning tasks to workers where each worker has different skill levels for different tasks.

Our goal is to make the assignments that'll maximize the total productivity.

Right, so it's just about getting things done, but getting them done as efficiently as possible.

Exactly.

Now, in the assignment problem, we've got a complete bipartite graph where each edge has a weight attached to it.

Our objective is to find a perfect matching that means every vertex on one side is paired up with exactly one vertex on the other side, such that the total weight of all the edges in the matching is the biggest it can possibly be.

Okay, so we're looking for the most set of pairings where everyone's matched up.

You got it, and the Hungarian algorithm is our secret weapon for finding this optimal solution.

All right, tell me about this Hungarian algorithm.

How does it work?

Well, it uses this concept of a feasible vertex labeling.

It's all about assigning a label, let's call it H, to each vertex in our graph.

Okay, so it's like giving each person or task a score.

Kind of, yeah, but there's a rule.

For any edge connecting vertex U on one side to V on the other,

the sum of their labels, plus H, plus HV, has to be less than or equal to the weight of that edge, WUV.

So it's like the combined value of the two vertices can't be greater than the value of the connection between them.

Exactly.

Now, this feasible labeling helps us define what we call the equality subgraph.

The subgraph includes only the edges where the sum of the labels is exactly equal to the weight of the edge.

So basically, we're picking out the connections where the values perfectly line up.

Ah, I see.

So we're focusing on the highest value connections where the scores add up perfectly.

Right.

And here's where theorem 25 .14c swoops in.

It states that if this equality subgraph has a perfect matching, then that perfect matching has to be the optimal solution for our original assignment problem.

It's the one with the biggest possible total weight.

So if we can find a perfect matching using only those equal value connections, we've hit the jackpot.

We've found the most valuable matching.

Precisely.

And the Hungarian algorithm helps us get there.

It starts with an initial feasible labeling and a matching, maybe even an empty one, just within that equality subgraph.

Then it tries to make this matching bigger by finding those M augmenting paths that we talked about earlier.

Right, those paths that connect unmatched vertices.

So it's like we're trying to grow our matching using only the high value edges.

Exactly.

But there's a catch.

We can only use the edges that are part of our current equality subgraph, the ones where the labels and weights match up perfectly.

So we're being picky about which connections we use to grow our matching.

What if we can't find one of those augmenting paths within those constraints?

Well, if that happens, the algorithm gets crafty.

It updates the feasible labeling, kind of like recalibrating those scores.

It does this in a way that brings new edges into the equality subgraph, the ones whose weight was just a tiny bit higher than the old labels.

So we're adjusting the values to bring in some new potential connections.

Exactly.

We're expanding the pool of high value options.

And this involves calculating a value called Delta, and then tweaking the labels of some vertices based on a breadth first search force that we built earlier.

Lemma 25 .15 comes in and assures us that these new labels are still feasible, meaning they still follow the rules, and importantly, that they've added at least one new edge to our equality subgraph.

So we can try again to find a bigger matching.

So it's this iterative dance between finding matchings within our high value subgraph, and then adjusting the values to bring in new connections if we get stuck.

You got it.

And eventually this process leads us to that perfect matching, that optimal solution using only those best edges.

Now, if you're into the nitty gritty details, the chapter even gives you the pseudocode for the whole Hungarian algorithm and its fine augmenting path subroutine.

Pseudocode.

So it's like a recipe for implementing the algorithm step by step.

Exactly.

It's all laid out for you.

And when we look at its performance, the initial version has a time complexity of O error.

But with some clever optimization, we can bring that down to O, making it a really efficient way to solve a wide range of these assignment problems.

That's amazing.

We've covered so much ground in this deep dive.

We started with understanding how to maximize the number of connections with the Hopcroft -Karp algorithm.

Then we explored the stable marriage problem and learned how the Gale -Shapley algorithm can create stable pairings while also potentially favoring one side over the other.

And finally, we tackled the assignment problem where we learned how to optimize those connections based on value using the Hungarian algorithm.

It's pretty incredible how this seemingly simple idea of matching leads to these really sophisticated algorithms that can solve some real world problems.

And it really makes you appreciate the power of algorithms and how these abstract ideas from graph theory can be applied to such practical situations.

It's a great reminder that sometimes the best solutions come from thinking about problems in terms of networks and connections.

So to our listeners out there, as you go about your day, think about this.

Where else might these concepts of maximizing connections, creating stability, or optimizing based on value apply in your life or work?

Maybe it's about teamwork, resource allocation, or even something completely different.

There might be some hidden opportunities to apply these ideas in unexpected ways.

And with that, I can confidently say we've covered all the major points, theories, findings, and examples from the chapter on matching and bipartite graphs.

We've delved into the definitions, the core algorithms, and the key themes that guarantee their effectiveness.

Awesome.

And that brings us to the end of another Deep Dive.

Thanks for joining us on this exploration of bipartite matching.

Until next time, stay curious and keep those connections strong.