| Line 28: | Line 28: | ||
So the original hiring problem can be reduced to a NP-complete problem in polynomial time, as showing in figure below. | So the original hiring problem can be reduced to a NP-complete problem in polynomial time, as showing in figure below. | ||
| − | [[File:Q4 NPcomplete.png| | + | [[File:Q4 NPcomplete.png|30px|Reduce job-seeking problem to NP-complete problem in polynomial time]] |
Revision as of 18:04, 20 July 2017
Computer Engineering(CE)
Question 1: Algorithms
August 2013
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 an NP-hard optimization problem. Its decision version, the vertex cover problem, was 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 $ peoples are seeking the jobs for this project, which requires a set of $ s $ specialist. Each candidate in the set $ s $ may have multiple expertise. We will model the the set of $ t $ applicants as $ V $ vertices, and each specialties they have will be modeled as edges from the 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.
