# Problem class of assigning N persons to N tasks, zero costs with prefs

I am looking for the general problem class / computational complexity / algorithms for the following problem:

N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice versa. There is a binary preferences matrix whose (i,j) entry is 0 if person i can not do task j, and 1 if it can.

There are no costs involved, no weights and the number of tasks equals the number of people.

I was searching for it but all I could find was the Assignment Problem which has costs/weights associated with each assignment.

As a last resort, perhaps I can transform my preferences matrix to a cost matrix if person can not do job then cost is infinite else cost is zero?

• This problem is exactly matching. Refer to Wikipedia for further details. – Lwins Jul 5 '19 at 18:43
• you mean "maximum bipartite matching" ( en.wikipedia.org/wiki/Matching_(graph_theory) ). i.e. construct a bipartite graph based on the prefs? Is max-flow the correct direction? – bliako Jul 5 '19 at 18:58

This problem is known as maximum matching of a bipartite graph. Basically let vertex $$p_i$$ (resp., $$q_i$$) represent the $$i$$th person (resp., task). And we connect $$p_i$$ and $$q_j$$ with an undirected edge iff person $$i$$ can do task $$j$$. The answer of the original problem is exactly the maximum matching of the new graph.
For algorithms, the classical Hungarian algorithm, of complexity $$O(n^3)$$, is a nice choice. Certainly you can reduce this problem to network flow, and then apply any max-flow algorithm. If you are looking for some "advanced" choices, refer to Wikipedia.