I have to prove that the following Recruiting problem a NPC-problem.

Input: n candidates and m positions and a matrix A $\in {Q^{n\times n}}$. Each entry $A_{ij}$ with i < j tells how much gets candidates i well with candidates j. and z

Question is there m candidates so that when we sum the corresponding $A_{ij}$ we are able to reach z

I want only a hint how to start, i somehow did not manage to find the known NPC problem to use my reduction

  • $\begingroup$ k-Clique can be reduced to it. $\endgroup$ – Albert Hendriks Jan 8 at 19:49

Your Answer

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

Browse other questions tagged or ask your own question.