CSEP 521: Applied Algorithms, Winter 2013

Hints on problem set 10

1. Page 505, ex 1, a, b

a. Yes. Since vertex cover is NP complete, there is a reduction from any problem in P to vertex cover, so there is a reduction from interval scheduling to vertex cover.

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.

2. Page 505, ex 2

For this type of problem, the key is to figure out what problem to reduce from. We want to have k customers, that don't share any products. This reminds me of Independent Set.

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.

3. Page 505, ex 3

For this problem, we want to find k counselors that cover m sports. Makes me think of k vertices covering m edges.

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.

4. Page 506, ex 4

a. The general problem is NP complete. This is a reduction from Independent Set. We respresent the vertices in the graph with jobs. If there is an edge between vertices v and w, we create a resource r_v,w that is shared between 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.

5. Page 507, ex 7

For 3 Dimensional Matching, see page 481. For 2 dimensional matching - the input is a collection of ordered pairs - and the question is if we can find n ordered pairs that cover all of the elements. Three dimensional matching is given a set of triples, and ask if there is a set of n triples that cover all elements. 3 dimensional matching turns out to be NP complete, while 2 dimensional matching is in P. (There are a number of examples where the "2" version of a problem is in P, while the "3" version of a problem is NP complete.

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].