11.2.2. Network Flows

We have some course allocation to be done in a school, we have a collection of teachers and we have a collection of courses and each teacher has indicated the preference of which courses he or she is willing to teach.

So, here we have 4 teachers Abbas, Chitra, Madan and Sunitha and we have four courses Math, History, Biology and Economics. So, Abbas for instance he is willing to teach History and Biology. Similarly, for Madan, he is happy to teach History or Economics. Each teacher has indicated a collection of courses that he or she is willing to teach.

In a school, we need to allocate courses to teachers based on their preferences. For example, we have four teachers who each have a set of courses they are willing to teach. Abbas is only willing to teach History and Biology, while Madan is happy with History or Economics. Essentially, each teacher's allocation is limited to the courses they are qualified or comfortable to teach.

Think of it like a potluck dinner where each attendee (teacher) brings a dish (course) they enjoy making. If someone only makes pasta, you wouldn’t expect them to bring salad or dessert unless they also enjoy making those.

This is what is called a matching problem, in particular it is called bipartite matching. So, what is a bipartite graph? Bipartite graph is which one in which the vertices come in two groups which we called v0 and v1 and all the edges go from v0 to v1. So, this program to the teachers are v0 and the courses are v1, now there are no edges between courses, there are no edges between teachers.

A bipartite matching problem divides into two distinct groups: teachers and courses. A bipartite graph has only connections (or edges) from one group to the other, meaning teachers can only connect to the courses they are willing to teach. There are no connections between teachers themselves or between courses, ensuring a clear structure for allocation.

Imagine two different teams at a sports event—let's say one team has players wanting to play basketball and the other has available courts. Each player can only play on their chosen court, and there's no communication between players on the basketball courts themselves.

If we have an equal number of nodes on each side in a bipartite graph, then we can expect or hope that everything on the left is matched to something on the right. This is what is called a perfect match.

In a bipartite graph where the number of teachers (nodes on one side) matches the number of courses (nodes on the other side), we can potentially assign each teacher a unique course. This is known as achieving a perfect match, where every teacher gets exactly one suitable course.

Consider a matchmaking service where each person is looking for a partner. If there are as many people (teachers) as there are potential partners (courses) and everyone is compatible, it’s possible for each person to find a partner, resulting in every single person being matched perfectly.

Here is how we can answer this question using network flows. We add a spurious source node feeding into the teachers and we add a spurious target node, a sink node coming out of the courses. Every edge in this has capacity one.

To solve the matching problem using network flows, we transform our bipartite graph by adding a source node that directs flow to the teachers and a sink node that receives flow from the courses. Each edge between these nodes is assigned a capacity of one, allowing us to model the allocation as a flow in the network.

Think of it as a water distribution system where water (flow) comes from a reservoir (source) and flows to different tanks (teachers) that can only hold a certain amount of water (one course). Lastly, the water flows into distinct sinks (courses), ensuring that one tank (teacher) does not receive more than one unit of water.

So, this is a general example of what we called a reduction. We want to solve a given problem, problem A, but we do not know how to solve it, but we do know how to solve another problem B.

Reduction involves converting one problem (problem A) into another (problem B) that is easier to solve. In our context, the matching problem (A) is converted into a flow problem (B). By using the flow algorithm, we can then derive the solution for the matching problem from the results obtained from the flow problem.

Imagine you’re trying to bake a cake (problem A), but don’t have the recipe. However, you know how to bake cookies (problem B). By converting the idea of baking a cake into baking cookies (like matching ingredients and steps), you can figure out the right steps to create your cake with the knowledge from baking cookies.

--