25.1.2. Modeling Job Assignments with Matching

So, let us begin with bipartite graphs and matching. So, just to recap in the last lecture we discussed what are bipartite graphs? They are the graphs where the vertex set can be partitioned into two disjoint subsets V1 and V2 where for each edge in the graph one of the end points is in the subset V1 and the other end point is in the subset V2.

A bipartite graph is a special type of graph where the set of vertices can be divided into two distinct groups. No two vertices within the same group are directly connected by an edge. Each edge connects a vertex from the first group to a vertex from the second group. Understanding this helps in visualizing relationships between two sets, which is crucial for solving assignment problems.

Imagine two groups at a party: one group consists of people who can cook, and the other group contains the dishes that need to be made. Each person (vertex) can make specific dishes (vertices). The edges represent which person can make which dish.

The job assignment problem is the following. Since we have to build a software, we have to ensure that each of the four modules namely Requirement, Architecture, Implementation, and Testing are taken care. So, we want to assign employees to do the jobs as per their skill set such that each job is attended by some employee.

In this problem, we need to allocate specific tasks (called modules) to employees based on their skills. Each task must be assigned to one employee, and no employee should handle more than one task at a time to ensure fairness. This scenario can be represented using a bipartite graph.

Consider a team of chefs in a kitchen where each chef specializes in one or more dishes. The head chef wants to assign each dish to one chef, making sure that no chef ends up cooking multiple dishes at once.

So, it is easy to see that one of the possible job assignments in organization 1 is the following. I take or I ask employee D to take care of the only job that it is capable of doing namely Requirement and then I take the employee B.

In this example, a valid job assignment can be constructed by selecting employees based on their skills. Employee D is assigned the Requirement module since it is the only module he can handle. Employee B, who has a broader skill set, can be assigned to a module where he can best contribute.

If Chef D can only bake bread and Chef B can make cakes, the head chef should assign baking the bread to Chef D and assign cake-making tasks to Chef B, leveraging each chef's unique skill.

But if you take the second organization it is not at all possible to come up with the job assignment in organization 2 satisfying these conditions.

In this scenario, despite various attempts to assign tasks based on available employees and their skills, it becomes evident that some tasks cannot be assigned without leaving at least one task unattended. This highlights the limitations and feasibility of job assignments.

If Chef X can only make appetizers and Chef Y only makes desserts, and you need a main course plus an appetizer, the task of preparing the main course goes unattended because neither chef can handle that task.

So, whatever we have discussed in this example can be modeled by a concept called matching. ... If I take the vertices of all distinct edges in my collection of edges M they should be distinct.

Matching in graph theory involves selecting edges such that no two edges share a common vertex. This is crucial for the job assignment problem where each task must be assigned to a different employee. A matching ensures that jobs are assigned without overloading any individual employee.

In our kitchen analogy, a matching would mean that no chef is assigned to cook more than one dish at the same time, ensuring that every dish has its own dedicated chef.

Now we have different types of matching. So, we have what we call as maximum matching and it is a matching which has the largest cardinality.

There are different types of matchings in graph theory: maximum matching, which has the largest number of edges, and maximal matching, which cannot be increased by adding more edges without violating matching conditions. It's important to distinguish between these types as they impact how resources can be allocated.

In our chef's example, maximum matching is like assigning as many chefs as possible based on their skills to complete as many dishes as they can, while maximal matching could mean assigning chefs in a way that no more assignments can be made without causing some chefs to take on multiple tasks.

Now we have another kind of matching called as complete matching ... a matching in this graph is a complete matching from V1 to V2.

A complete matching ensures that every vertex in one subset (e.g., employees) is matched with exactly one vertex in the other subset (e.g., job modules). This is the ideal scenario for the job assignment problem because it maximizes coverage of tasks.

It’s like ensuring that every dish at a banquet is being prepared by a dedicated chef, where each chef is responsible for a specific dish without any overlap in duties.

So, to understand the necessary and sufficient condition given by the Hall's marriage theorem. ... the number of neighbors of that subset A should be greater than equal to the number of nodes in the set A, |N(A)| ≥ |A|.

Hall’s marriage theorem provides a condition under which a complete matching exists in a bipartite graph. It asserts that for any subset of vertices from one group, the number of adjacent vertices in the other group must at least equal the size of the subset. If this condition holds for every subset, a complete matching exists.

Consider a matchmaking event where each boy must find a girl to match with. Hall’s theorem ensures that for every selected group of boys, there are enough girls available based on their preferences, so everyone can potentially find a match.

--