I have the following problem I am trying to prove NP Complete.

Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ classes.

The tutors rent a large study room to offer help to students. But, note that ALL tutors for a specific class can't be in the study room. Otherwise, that class will have no one left to grade the exams.

Question is, can we have $k$ tutors in the study room?

Attempt at solution:

I feel like this is a set or vertex cover problem and have interpreted as follows. We create a bipartite graph... connecting the left hand side (class) to right hand side (tutor). We have to see if we can choose $k$ tutors from the right hand side such that no left hand side vertex has all its edges used up.

enter image description here

For example, if $k = 1$ the answer is yes. Choose any person. If $k = 2$ answer is yes. $\{A, D\}$ works but not $\{A, B\}$ because they make up the tutors for $C2$. $k = 3, 4$ also do not work for the same reasoning.

I am trying to decide if I should approach this with set-covers, clique, independent set? I'm not entirely sure but feel this approach is on the right track.


You can prove this by a reduction from the Hitting Set problem (which is NP-Complete):

Given a base set $U$, a family $F = \{S_1,\ldots,S_\ell\}$ of subsets of $U$ and an integer $q$, decide if there exists a set $H$ of size at most $q$ which intersects every set in $F$ (this is called a hitting set).

So suppose given an instance of the Hitting Set problem. For every element in $u\in U$, create a new TA $T_u$. For every set $S\in F$, create a new class $C_S$ whose TAs correspond to the elements in $S$. Let $k = |U|-q$.

Then if you interpret the TAs being left out of the room as the elements chosen in $H$ it is not hard to see that there exists a hitting set of size at most $q$ if and only if you can put $k$ TAs in the room. That is because putting $k = |U|-q$ TAs in the room is equivalent to leaving at most $q$ outside of the room. And hitting every set in $F$ is equivalent to having at least one TA per class left out of the room.

(I leave the formal proof up to you)

  • $\begingroup$ I do have a brief follow up. Using Vertex Cover reduction, suppose we have 3 courses and 4 TAs. The TAs for these courses are subsets (a, b, c) (a, c) and (a, c, d). Clearly, we could exclude only person "a" and have a valid output. But from a vertex covering perspective, excluding "a" would not form a vertex cover over this graph. $\endgroup$ – rubyquartz Dec 7 '19 at 21:48
  • $\begingroup$ I'm not quite sure what you are saying, as I didn't reduce it from the Vertex cover problem but from the Hitting Set problem (which is not the same). But you are right about the fact that the reduction from Vertex Cover you are proposing doesn't work. $\endgroup$ – Tassle Dec 7 '19 at 22:16
  • $\begingroup$ I suppose my main question is if vertex cover in some form could be used for a formal proof, or if you would suggest another known NP complete problem to prove by reduction. Mainly because I understand your answer, but I'm having some difficulty choosing the right NP complete problem to start a proof. $\endgroup$ – rubyquartz Dec 7 '19 at 22:50
  • $\begingroup$ Actually, now that I think about it, reduction from Vertex Cover does work, you're simply doing it the wrong way around. For a graph $G=(V,E)$, let the set of TAs be $V$ and let the set of classes be $E$. Now there is a vertex cover of size at most $|V|-k$ if and only if there is a TA assignment with at least $k$ TAs in the room. $\endgroup$ – Tassle Dec 7 '19 at 23:50
  • $\begingroup$ In this case the example you gave doesn't correspond to any graph we could start with, so this is not a problem. $\endgroup$ – Tassle Dec 7 '19 at 23:51

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.