Computer Engineering(CE)
Question 1: Algorithms
August 2013
Back to QE CE question 1, August 2013
Problem 4. A project management firm needs to hire technical experts for a project with requires $ s $ different specialist. The project requires at least one expert in each of the specialties. The firm has received job application from $ t $ potential individuals. An applicant may have multiple areas of expertise. For each of the $ s $ specialties, there is some subset of the $ t $ applicants qualified in the required technical areas. For a given number $ k<t $, is it possible to hire at most $ k $ applicants and have at least one expert qualified in each of the $ s $ specialties? Prove or disprove that this problem is NP-Complete.
Solution 1
This is a NP-Complete problem, because this problem can be reduced in polynomial time to vertex cover problem, which is a known NP-Complete problem.
Proof: A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of a NP-hard optimization problem. Its decision version, the vertex cover problem, is one of Karp's 21 NP-Complete problems and is therefore a classical NP-Complete problem.
In order to prove that the hiring problem here is NP-Complete, we need to construct a graph for this problem first.
Suppose that a set of $ t $ people are seeking jobs for this project, which requires a set of $ s $ specialists. Each candidate in the set $ s $ may have multiple expertise. We will model the set of $ t $ applicants as $ V $ vertices, and each specialties they have will be modeled as edges from one vertex to a dummy vertex. If any two of the experts have the same specialties, then those edges will be combined as one, which will be an edge connecting between the two experts(vertices). The minimum number of experts that covers every specialties will be equivalent to the problem of the minimum number of vertices $ V_{min} $ that each edge is incident to at least one vertex, or in other words, find the minimum vertex cover. For a given number $ k<t $, if $ k>=V_{min} $, then it is possible to hire at most $ k $ applicants and have at at least one expert qualified in each of the $ s $ specialties; otherwise, it is NOT possible. So this hiring problem can be reduced to a minimum vertex cover problem (NP-Complete) in polynomial time, so it is NP-complete.
So the original hiring problem can be reduced to a NP-complete problem in polynomial time, as showing in figure below.
Solution 2
Vertex Cover is known to be NP-Complete. Vertex Cover problem: We have a graph $ G = (V,E) $ and a number $ k $, need to find out if $ G $ contains a vertex cover of size (at most) $ k $. Need to reduce the vertex problem to this recruiting problem.
To prove vertex cover $ \leq_p $ recruiting problem:
- Assign each expert a node and each edge represents some specialty.
- Each expert is qualified in the specialty on which the edge is incident on their expert node.
- Suppose a black box for recruiting problem, so to see if there is a subset of $ k $ experts that are qualified in all specialties.
- The black box for recruiting will return 'yes': there is a subset of $ k $ experts that are qualified in all specialties. So every specialty edge is incident on at least one node in the set of nodes corresponding to the expert subset. Hence, this set of nodes is a vertex cover of size $ k $.
- The vertex cover problem is 'yes': Graph $ G $ contains a vertex cover of size $ k $. Then for the subset of experts that are assigned to the nodes in the vertex cover, each sport edge is incident on at least one node in the vertex cover, so there is a subset of $ k $ experts corresponding to the vertex cover nodes that are qualified in all sports. The black box for recruiting will return 'yes'.
Vertex cover requires polynomial time to construct the problem as an recruiting problem and polynomial calls to the recruiting black box. Hence, vertex cover $ \leq_p $ recruiting problem. So, it is NP-Complete.
Comments on Solution 2:
It is the right approach to reduce the hiring problem to some known NP problems in polynomial time. However, the construction of the graph is not clear in solution 2. If there are multiple experts who have the same speciality, this construction of the graph does not tell us how to handle that. For example, assume there are three experts that have the same speciality. It is trivial to see that any of the expert will be a minimum vertex cover. However, using the strategies that described in the solution 2, each expert will be modeled as a vertex, and one edge represents as the speciality. We don't know how to connect one edge to all of the three vertexes.
