Consider a problem PROB1 which takes as input a number k, a set of words W, a collection of n documents using words from W {D1 ... Dn}. PROB1 has to decide if there are at most k documents which collectively contain all the words in W.

Consider a problem PROB2 which takes as input a number m, a set of words W, a collection of n documents using words from W {D1 ... Dn}. PROB2 has to decide if there is a set of at most m words such that every document has at least one word from this set.

Consider a problem PROB3 which is given two number a and b, and a bipartite graph G=(L U R, E) where L and R denote the vertices in the left and the right partitions, respectively, and the edges in E have one endpoint in L and the other endpoint in R. PROB3 has to decide if E contains a subset E' such that {x : x is an endpoint of some edge in E'} has at least a vertices from L and at most b vertices from R.

(a [8 points]) Show that PROB1 <= PROB3.
(b [7 points]) Show that PROB2 <= PROB1.

Assume that |W| = n^4 (the number of words). There is no information on the number of words in each document, except the trivial upper bound of |W|. The running times of the reductions should be polynomial in n and k ( there is no deduction of points for designing a slower reduction as long as it is of polynomial complexity, or coming up with sloppy analysis, as long as it is a polynomial). You can also assume that the documents Di's are given as enumerable lists of unique words appearing in them, i.e., " for word w in Di: // do something with w" is a valid way to process all (unique) words in a document.