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?


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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.