# choose minimum number of M professors in polynomial time in order to design all N course exams

Think that we have M professors and N courses every professor can wrote question for at least one course exam. we want to choose minimum number of professors in order to design question for all N courses exams.

I try to hard but I only could model this question in a bipartite graph that one sections are professors and the other sections includes courses every professors are connected to every courses that they can design question for them.

we wish to choose minimum professors to cover all courses. one easy method is to check all cases and pick the minimum one in exponentioal time order...

could any one help me to solve it in polynomial time?

thanks

• You can't solve it in polynomial time. Read about the "Set Cover" problem. May 20 '16 at 9:21
• Check this. May 20 '16 at 9:26

## 1 Answer

It's a variant of Set cover which is Classical NP-Complete problem. Here is the problem definition.

Reduction: Take All courses as a Universal set U which you want to cover. Then make collection of sets $S=\{P_1,P_2,...,P_m\}$ where, $P_i$ is the set of subjects for which a professor $i$ can design a question. and you can go similarly in reverse direction.

So there is no polynomial time algorithm for your problem unless P=NP.