Algorithm - A variant of Maximum Bipartite Matching

Question

I am dealing with a variant of the Maximum Bipartite Matching problem. The original problem is as the following:

There are M job applicants and N jobs. Each applicant has a subset of jobs that he/she is interested in. Each job opening can only accept one applicant and a job applicant can be appointed for only one job. Find an assignment of jobs to applicants in such that as many applicants as possible get jobs.

The additional constraint is that:

Each applicant belongs to a certain group. Now, instead of maximize the number of applicants, we want to maximize of number of happy groups. A happy group is a group in which all of its applicants can get a job.

Any ideas/discussions are welcome!

Answer 1

Connection to Eternity

If you could solve this, you could have won a million pounds on the Eternity puzzle.

In this puzzle you have to fit 209 polygons onto a board.

The reduction is to have one group for each combination of piece and location.

Each group has a leader who is only interested in the job that corresponds to playing his piece.

Each group also has a person for each square in the tile: that person is only interested in the job of filling the corresponding square on the game board.

If you can find a solution with 209 happy groups then you have found a solution to the puzzle!

Connection to Independendent set

This is NP-hard because it can be used to solve maximum independent set which is a known NP-hard problem.

Suppose we have a graph in which we want to find the maximum independent set.

Make a job for each edge.

Make a group for each vertex.

Suppose vertex x is connected to three edges a,b,c. We would add 3 people to group x. Each person is only interested in one job. The first is interested in job a, the second in job b, the third in job c.

Finding the maximum happy groups is then equivalent to the largest independent set.