| Line 30: | Line 30: | ||
[[File:Q4 NPcomplete.png|800px|Reduce job-seeking problem to NP-complete problem in polynomial time]] | [[File:Q4 NPcomplete.png|800px|Reduce job-seeking problem to NP-complete problem in polynomial time]] | ||
| + | ---- | ||
| + | ===Solution 2=== | ||
| + | Vertex Cover is known to be NP-Complete. Vertex Cover problem: We have a graph <math>G = (V,E)<math> and a number <math>k</math>, need to find out if <math>G</math> contains a vertex cover of size (at most) <math>k</math>. | ||
| + | Need to reduce the vertex problem to this recruiting problem. | ||
| + | |||
| + | To prove vertex cover </math>\leq_p</math> recruiting problem: | ||
| + | |||
| + | \item Assign each expert a node and each edge represents some specialty. | ||
| + | |||
| + | \item Each expert is qualified in the specialty on which the edge is incident on their expert node. | ||
| + | \item Suppose a black box for recruiting problem, so to see if there is a subset of $k$ experts that are qualified in all specialties. | ||
| + | \begin{enumerate} | ||
| + | \item 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$. | ||
| + | \item 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. | ||
[[ECE-QE_CE1-2013|Back to QE CE question 1, August 2013]] | [[ECE-QE_CE1-2013|Back to QE CE question 1, August 2013]] | ||
[[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]] | [[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]] | ||
Revision as of 19:36, 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.
Solution 2
Vertex Cover is known to be NP-Complete. Vertex Cover problem: We have a graph $ G = (V,E)<math> and a number <math>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 </math>\leq_p</math> recruiting problem:
\item Assign each expert a node and each edge represents some specialty.
\item Each expert is qualified in the specialty on which the edge is incident on their expert node. \item Suppose a black box for recruiting problem, so to see if there is a subset of $k$ experts that are qualified in all specialties. \begin{enumerate} \item 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$. \item 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.
