In question 2, we are asked to show a reduction from VERTEX-COVER to MINESWEEPER
In class we defined VERTEX-COVER as {<G,k> | G has a vertex cover of size <= k}
We are asked to consult the proof of the reduction from VERTEX-COVER to SUBSET SUM.
However, in that book, as can be seen here (section 36.5.2) VERTEX-COVER is defined as {<G,k> | G has a vertex cover of size = k} (note the = and not <= ). This is important to the proof of the reduction. The reduction shown in the book does not work for VERTEX-COVER as defined in class (<= k), since if G has a vertex cover smaller than k, then <G,k> will be in VERTEX-COVER (as defined in class), yet the reduction will yield a <S,t> such that S' will not amount to t (it will amount to t', which is almost like t, but the highest digit is not k, but smaller than k).
This seems to effect question 2.b and c as well. In (b) it is implied that k should be assigned to one of the vertices.  Assigning k to ANY of the vertices will result in a non satisfiable MINESWEEPER instance - since one can give (G, 10000000000) with |V| = 10 and it will be in VERTEX-COVER as defined in class - yet will not be satisfiable.
In summary, it seems that question (2) as well uses the definition of VERTEX-COVER as (=k) and not (<=k). Can you clarify this issue for us? For now, we cannot continue with the problem.


With thanks, Dor and Tsah.