My problem is:

There is an input list of 5 children and a list of chores that they would prefer to complete.

Let days be equal to 10, and for each day, there are 2 chores that they must complete.

There are restraints where each child must complete at least 3 chores and at most 5 chores, each chore must only be completed by 1 child, and no child is allowed to complete both chores in a day.

My goal is to find an allocation where each child is allocated the chores where this allocation satisfies the restraints above.

I understand that I can create a bipartite graph with vertices u_i corresponding to children, and v_j corresponding to chores. Then, I can draw edges from vertices u_i to v_j corresponding to each child's preference to each chore. I understand these edges will have a capacity of one (as each chore can only be completed once). Furthermore, I know to add a start vertex, with an edge from each vertex u_i to the start vertex, and also to add a sink vertex, with an edge from each vertex v_j to the sink vertex.

However, I am confused about how to implement the restraint where each child must complete at least 3 chores and at most 5 chores. Where does this restraint fit on this bipartite graph?

I would appreciate any help! Thanks!

CodePudding user response：

There is a total of 20 tasks to complete (2 each day). Each child must complete 3 of those 20, and up to 5. That means that when each child has done his minimum of tasks, 5 remains to be done.

• Make the edge from the source to each child with a maximum capacity of 3.
• Make a vertice rt (remaining tasks"), with an edge from the source to rt with a capacity of 5, and some edge from rt to each child, with a capacity of 2 (each child can only complete 2 of the 5 remaining tasks)

With this setup, there is a total capacity of 20, so if all 20 tasks are completed, it is forced that each child do 3 of them.