b. Maybe. This is a bit of a trick question. If there is a polynomial time reduction from vertex cover to interval scheduling then vertex cover is in P, so P = NP.
To reduce from Independent Set to Diverse Subset, we use the matrix to represent the incidence matrix of the graph. We start with the graph G = (V,E) that we want to find the independent set in. If (v,w) is in E, then we create a product p_v,w that is purchased only by v and w. A diverse subset corresponds to an independent set in the original graph.
Reduction of Vertex Cover to Efficient Recruiting. The vertices are represented by counselors. If we have an edge between v and w, we create a sport s_v,w that can only be coached by v and w.
b. If k = 2, we are just finding if there are two jobs that don't share any resources. We can do this by brute for, just checking every pair of jobs.
c. With the two types of resources, the problem can be represented as a bipartite graph, where a job is an edge between a person and an equipment. The problem can be solved with bipartite matching in polynomial time.
d. NP complete. The reduction given in part A uses resources shared by just two jobs.
To show 4 dimensional matching is NP complete, we want to reducte from 3 dimensional matching. The trick is to just pad each triple with an extra coordinate. We need to do this in a way that we don't really change the problem. One way to do this is to just repeat the last coordinate - so that the triple [a, b, c] is mapped to the quadruple [a, b, c, c].