Discussion 11: Using DFS for Bipartite Matching

In lecture, we discussed graph traversal algorithms such as Breadth-First Search (BFS) and Depth-First Search (DFS). These procedures allow us to explore graphs in different ways. DFS, going as far as possible along each branch before backtracking, is useful for finding a path out of a node with some desired property. In this discussion, we’ll use a variant of DFS to find augmenting paths in bipartite graphs to solve the maximum matching problem (more on all of this below).

Learning Outcomes

• Translate between a formal description (list of vertices, edges) and an illustration of a (weighted) graph.
• Identify substructures in graphs such as neighborhoods, paths, and cycles both visually and programmatically.
• Perform BFS and DFS traversals of a given graph by hand and in code.

Reminder: Discussion Guidelines

The work you complete in discussion serves as a formative assessment tool, offering the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going, so we can make adjustments in future classes. Your grade in discussion is based entirely on attendance and participation; if you show up and you are actively engaged with the activity (working on the activity on your computer, discussing the activity with your group, asking and answering questions, etc.) for the entire 50-minute section period, you will earn full credit. If you complete the activity early, helping other students is a great way to further your own understanding. You do not need to submit any of the work that you complete during discussion.

Since discussion activities are not graded for correctness, we do not place any restrictions on resources that you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from critically thinking to “puzzle” them out.

Working together in small groups is encouraged during discussion!

Bipartite Matching

Bipartite Graphs

Sometimes, the vertices in a graph can be naturally divided into two disjoint sets (referred to as its left and right vertex sets), so that every edge connects one vertex from the left set with one vertex from the right set; there are no edges between two left vertices or between two right vertices. We call these graphs bipartite (meaning two-parted).

In lecture, we discuss graphs with directed edges. However, bipartite graphs typically have undirected edges. This means that we can represent the edge both as (A,B) and (B,A). For this discussion, we’ll only consider unweighted edges.

Example Bipartite Graph :

Matchings

A matching in a graph is a subset of its edges that share no common vertices. In other words, each vertex belongs to at most one edge within a matching. We call these sets matchings because each edge matches its two vertices (in our example, it matches a pilot with a plane they are qualified to fly).

Augmenting Paths

A key tool that we can use to programmatically construct maximum matchings is an augmenting path. Given a matching \(M\), an augmenting path for \(M\) is a path that:

• Starts with an unmatched vertex,
• Ends with an unmatched vertex,
• Alternates between edges that are not in \(M\) and edges that are in \(M\) (so if one edge is in the matching, the subsequent one will not be, and vice versa)

We can use augmenting paths to iteratively build up a maximum matching to add pairs. Notably, one can show that a matching is a maximum matching if and only if the graph does not contain an augmenting path for \(M\).

When we locate an augmenting path, we can use it to increase the size of our current matching by 1. To do this, we flip the matched/unmatched status of all the edges along this path.

Example:

Let’s say we already have a matching of {(Alpha, P1), (Bravo, P2)}. The pilots that remain unmatched are Charlie and Delta, and the planes that remain unmatched are Planes P3 & P4.

1. We can easily see that we could add Charlie matched with P3 since that is an unmatched edge starting and ending with a free vertex (unmatched).

If we take that augmenting path, we make (Charlie, P3) a matched edge. Now, we have only Delta and P4 as unmatched.

2. Now, let’s look at Delta (remaining unmatched). There’s an augmenting path from Delta \(\to\) P2 \(\to\) Bravo \(\to\) P4. Let’s verify it is an augmenting path:
   

• Delta is unmatched
• P4 is unmatched
• This path alternates between edges not in and in the matching. The first edge is unmatched, the second edge is matched, and the third edge is unmatched, so we alternated correctly.

This means that it is an augmenting path. To take this augmenting path, we will change (Delta, P2) to being a matched edge, (Bravo, P2) will change to unmatched, and (Bravo, P4) will change to matched. Essentially, we are unmatching Bravo from P2, allowing it to match to P4 while Delta matches to P2. Our matching is now {(Alpha, P1), (Bravo, P4), (Charlie, P3), (Delta, P2)}.

We have increased our number of pairs by one and located a maximum matching; there are no more unmatched vertices, so there can be no more augmenting paths.