25.1.1. Job Assignment Problem

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 into the subset V1 and the other end point is in the subset V2. And it turns out that bipartite graphs are very important class of graphs used to model various real-world problems.

Bipartite graphs are a specific type of graph where the set of vertices can be divided into two distinct groups. This means that edges only connect vertices from different groups, but not within the same group. For example, in a bipartite graph representing employees and their skills, one group might consist of employees, while the other group consists of skills required for a project. Each edge represents an employee's capability to perform a specific skill.

Imagine a classroom where students are on one side and subjects are on the other. A student who excels in Math would have a line (edge) drawn to the Math subject. No student is connected to another student; instead, they’re all connected to the subjects they can teach or study.

And one of the problems for which they are used extensively is that of job assignment. So, let me demonstrate the job assignment problem with this example. Imagine you have two organizations, organization 1 and organization 2. Both of them are trying to build a software and say the software has four modules: Requirement module, Architecture module, Implementation module, and Testing module.

The job assignment problem involves assigning tasks to employees based on their capabilities, ensuring that each task is completed by someone who is suitable for it. In the given scenario, there are two organizations working on the same software, each with employees (from Organization 1: A, B, C, D) who can tackle different modules needed for the software. The aim is to assign these employees to the respective modules efficiently.

Think of a team project where each team member has different strengths—one person is great at coding, another at designing, and someone else excels in testing. The project leader must assign tasks so that each person is working on what they are best at. That way, the project will progress smoothly, and everyone feels competent.

So, we want to assign employees to do the jobs as per their skill set such that each job is attended by some employee. But at the same time we do not want to be very strict or unfair with an employee by assigning multiple jobs as per its skill set.

In this problem, there's a key constraint: no employee should be assigned more than one job. This ensures that the workload is fairly distributed and no one is overloaded. The challenge is to make sure that every job (module) gets done while respecting this limitation.

Imagine a group of friends planning a party with different chores like decorating, cooking, and cleaning. They agree that no one should be stuck doing too many tasks, so each friend takes one job. This keeps things fair, and it makes sure all chores are covered.

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. So, employee B can handle Architecture, Implementation, and Testing. So, I choose architecture for employee B.

Here’s a practical example of how assignments can be made. Employee D is assigned to the Requirement module. Employee B, talented in multiple areas, is assigned to the Architecture module, illustrating how we match tasks to appropriate employees based on their strengths. Employee C and A would then be matched to their respective modules, ensuring all necessary tasks are allocated without overburdening any single employee.

In the cooking example, suppose Jamie is assigned to set the table (Requirement), while Chris handles the main dish (Architecture). Both are working on tasks that play to their strengths, and other friends can take on different tasks too, completing the preparations for the party successfully.

However, in this whole process, in this scheduling, the module Implementation is not assigned to any employee. It goes unattended. And you can try other possible combinations as well. You will see that irrespective of the way you try to assign the jobs you cannot come up with a job assignment satisfying these conditions.

Despite trying different combinations of task assignments, the example illustrates that it’s not always possible to cover every job with the given employee skillset without violating the constraints. In this scenario, some skills are in excess and cannot be matched effectively to the available employees, highlighting a limitation in the assignment problem.

Returning to our party example, even if Jamie and Chris cover some tasks well, if they both can cook but happen to dislike setting the table, no one might be available to do it, leaving it incomplete and creating a gap in the planning.

So, whatever we have discussed in this example can be modeled by a concept called matching. So, imagine you are given a simple undirected graph. A collection of edges denoted by M is called a matching if no two edges in this collection of edges M are incident with the same vertex.

In graph theory, a matching refers to a set of edges that do not share any vertices, meaning that no employee can be assigned more than one job, as discussed earlier. This forces the designated edges to represent distinct assignments in the context of the job assignment problem.

Think of matching as pairs in a game of pairs; two nodes are connected if they represent a valid assignment. If you have two connected, everyone is paired off correctly without any overlaps—every employee and task gets exactly one connection.

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 various types of matching within graphs. Maximum matching refers to the largest possible selection of edges in which no two edges share a vertex. In simpler terms, it's the biggest matching possible without creating whole overlaps, maximizing the number of assignments while still abiding by the rules.

Consider a dating service where maximum matching means arranging the highest number of couples without anyone being paired off with more than one partner. The aim is to make the best connections possible while keeping it fair.

Now we have another kind of matching called as complete matching... the necessary and sufficient condition for checking whether there exists a complete matching in a given bipartite graph or not.

Hall's Marriage Theorem provides a criterion to determine if there exists a complete matching in a bipartite graph. In essence, it states that for every group of nodes, the total number of neighbors must be equal to or greater than the number of nodes within that group. This ensures that every 'task' can be covered by a unique 'employee'.

Relating to our earlier examples, imagine a wedding where every person (boy) must find a partner (girl) among their preferences. Hall's theorem acts as a matchmaker. If for every subset of boys you can identify enough girls willing to pair with them, the marriage is feasible; otherwise, it isn't.

--