Efficient Recruiting and Algorithm Design: Set Cover, Hamiltonian Path, and Longest Increasing Subsequence

Set Cover to Efficient Recruiting

Input: Set U of elements, collection S₁, ..., S_m of subsets of U, integer k ≥ 0

Construct an instance of the Efficient Recruitment Problem:

• Sports are represented by U.
• Applicants are represented by {1, ..., m}.
• For every s ∈ U and 1 ≤ i ≤ m, M[s, i] = 'qualified' if s ∈ S_i and 'not qualified' otherwise.

Steps:

1. Call the oracle for Efficient Recruiting with input M and k.
2. Return the result (yes or no) of the previous call.

Vertex Cover and Hitting Set

Graph: G = (V, E)

• U = V(G)
• S_i = {u, v}, where (u, v) is an edge of G.

Vertex Cover ⇒ Hitting Set:

If C is a vertex cover for G of size k, then by definition, for every edge (u, v) in G, either u ∈ C or v ∈ C. Therefore, C is a solution for Hitting Set because it must intersect every set S_i.

Hitting Set ⇒ Vertex Cover:

Now suppose H is a hitting set of U of size k. Since H intersects every set, it has at least one endpoint of every edge. Set C to be H.

Verifier for Exam Scheduling Problem

- lists l1, . . . , ln,
- lists a_11, . . . , a_10 where each list a_i is a subset of {1, . . . , n} {a_i encodes the courses whose exam is scheduled in day i}
.Check that every course is scheduled in exactly one day and that every pair of courses scheduled in the same day do not have any student in common **
9 - input: a graph G
.pick any arbitrary node v from G
for each node u adjacent to v do
     .Construct a new graph H in the following way: Initially, place in H all nodes and edges in G. Furthermore, we add to H two new nodes, that we call u' and v', and the new edges (u', u) and (v',v)
     .Call the oracle for Hamiltonian Path with input H.
     .if the result of the previous call is yes then
          stop and return yes
     .end if 
.end for
retur n no
Let Y be a NP-complete. We have mentioned in class that Y belongs to P if and only if P=NP. In this exercise we ask you to prove it.
(a) If Y belongs to P then P=NP. Assume that Y belongs to P. Let X be any problem in NP.  Since Y is NP-complete it follows that X (

)>)>
(b) If P=NP then Y belongs to P. This is immediate. Assume that P=NP. Since Y belongs to NP and P=NP then Y belongs to P as well
Algorithm LIS
1: input: A sequence A[1], . . . , A[n] of integer numbers
2: for j := 1 to n do
3:    M[j] := 0
4:    for i := 1 to j − 1 do
5:       if A[i]
6:          M[j] := max(M[j], M[i])
7:       end if
8:     end for
9:     M[j] := M[j] + 1.
10: end for
11: {Finally, it is only necessary to find the maximum value in M}
12: maximum := 0
13: for j := 1 to n do
14:     maximum := max(maximum, M[j])
15: end for
16: return maximum