Throughout this write-up, we use "x" to refer to the input to the problem we are reducing from and "T(x)" to refer to the input created by the transformation. Also, in all cases I don't discuss that T(x) is computable in polynomial time but it is easily verified that this is the case. While most of the key portions of the proofs are there, this is intended to be sure you understand the solution and is not intended to have the complete proofs. Look at the provided homework solutions and typeset practice problems if you are looking for examples of how to write-up your solutions.
To prove GOLD-DIGGER is NP-hard, a reduction from HAM-CYCLE can be used. Here is the reduction. Let G be the input graph for HAM-CYCLE. For the GOLD-DIGGER input the graph G' will be obtained from G by adding a self loop for every vertex in G. All of the original edges in G will be given weight of 1. Each edge added to G' (i.e. the self loops) will be given weight 2(|E|+1). Each town will have a cost of |E|+1. Finally, let the desired profit J = |V|. As an excercise I encourage you to proof this works. Here are the highlights. To prove x in HAM-CYCLE -> T(x) in GOLD-DIGGER, you can just take the HAM-CYCLE and to make it a GOLD-DIGGER solution, just include the self-loop from each vertex to itself each time a vertex is reached. There are |V| original edges (each with profit 1) used. Note that each vertex is visited twice, so has cost 2(|E|+1) which is covered by the gold on the self loop. So the profit is exactly |V|.
To prove T(x) in GOLD-DIGGER -> x in HAM-CYCLE, take an expedition for the gold-digger that has profit of |V| or more. Observe that in order to obtain the gold on any self-loop, one has to spend that profit to pay to stay at the town from which the self-loop originates. If one would ever visit any town twice then the profit would be negative since there are only |E| edges with profit 1 available and even if you would reach them all, the profit would be negative since the cost of a town is |E|+1. Thus the gold-digger expedition never revisited a town. However, to get a profit of at least |V| then at least |V| of the original edges must have been traversed and by definition, a cycle that visits |V| edges without revisiting a vertex is a HAM-CYCLE. So the expedition when the self-loop are removed is a HAM-CYCLE in G. We'd be happy to look over your proof or help you in writing one if needed. Note, that the above reduction assumes that in the town where the gold digger begins (which can be arbitrarily select as any vertex in G'), he pays the cost of staying there twice. If that is not the case then the weight on the self loop out of the starting town can be adjusted accordingly. Also, there are other valid reductions that can be given. If you have a different one that you'd like us to look at, bring it by our hours (or email it).
To prove T(x) in FVS -> x in VC, let V' be a solution to FVS. We now prove that V' is a VC in x. Suppose note. Let (u,v) be an edge in G for which neither u or v is in V'. However, (u,v) in G is transformed into the edges u --> v and v --> u in G' and this is a directed cycle where neither u or v are in V' (the FVS solution) which is a contradiction to V' being a FVS solution.
Showing VC <=_p FVS does not prove that FVS is NP-complete. It just proves that FVS is NP-hard. To prove it is NP-complete you would also have to prove that FVS is in NP (which could easily be done).
We now give a counterexample to prove that it is possible for G' to have a ham-cycle when G does not have a directed ham-cycle. The counterexample is obtained by adding the edge c --> b to the example drawn. It is visually easy to see that there is a ham-cycle in G' but no directed ham-cycle in G.
The problem with the reduction is that the intention was that any solution for G' would always go from v_in directly to v_out but there is nothing in the transformation to enforce this. The counterexample is created by having the ham-cycle go from b_in to c_out, then to c_in, and then to b_out. THis can be remedied, by replacing the edge {v_in,v_out} by the pair of edges {v_in,v_mid},{v_mid,v_out}. I'll leave it as an exercise for you to prove this fixes the reduction.
We now prove that 3-CNF-SAT <=p SIP. Let C_1 ^ C_2 ^ ... ^ C_m be the 3-CNF-SAT input with C_i is a clause and "^" is being used as the conjunction symbol. Let x_1, ..., x_n be the boolean variables. There will be 2n objects x_1,....,x_n,y_1,....,y_n used in SIP where the correspondence we will create is that y_i corresponds to the negation of x_i. So whenever !x_i occurs, SIP will use y_i in its place.
There will be m finite sets A_1, ..., A_m, where A_i contains the 3 literals of C_i. So if C_1 = x_2 v !x_4 v x_5 then A_1 = {x_2,y_4,x_5}. There will be n sets B_1, ... B_n where B_i = {x_i,y_i}.
We now prove that this works. First I'll argue that x in 3-CNF-SAT -> T(x) in SIP. Take a satisifying assignment for x and let T (the SIP solution) contain the set of literals that are true. So T will contain x_i if x_i is true and y_i if x_i is false. Thus |T|=n. Since we began with a satisfying assignment, at least one literal in each clause is true, and hence T will contain at least one element of each A_i. Since exactly one of x_i and y_i are in T, it follows that for each B_i, |T intersect B_i| = 1 <= 1 as required.
We now prove that T(x) in SIP -> x in 3-CNF-SAT. Let T be the solution to SIP. Since |T intersect B_i| <= 1, T cannot include both x_i and y_i for any i. It could include neither. We create a satisfying assignment for x as follows. If x_i in T set x_i=1, else set x_i = 0 (so we do this if y_i in T or neither are in T). We now argue this is a satisfying assignment. By construction each variable is set to true or false. We now argue each clause C_i is satisfied. Since |T intersect A_i| >= 1, for each A_i, at least one of those elements are in A and the correpsonding literal is true in the satisfying assignment.
We now prove Partition <=_p 2-MIN-CLUSTER. Let (x1,...,xn) be the input to partition. We create the following graph with n+1 vertices. There will be vertices v,v1,v2,....,vn. There will be n edges, one from v to vi for i=1,...,n. The weight of the (v,vi) edge will be xi. Finally, k = (x1 + ...+ xn)/2. If k is not an integer (meaning the answer to partition is no), then instead create the SIP input with one edge between vertices u and v with weight 2 and let k=1. Clearly, the answer for this SIP solution is no. So we now focus the proof on when k is an integer.
We first prove x in Partition -> T(x) in 2-MIN-Cluster. Let S be the subset of the n items that add to (x1 + ... + xn)/2. We now argue that the partition where V1 contains v and all vi such that i in S and V2 contains all vi where i not in S is a solution to partition. Observe that w(V1,V2) = sum_{i in S} xi = k.
We now prove T(x) in 2-Min-Cluster -> in Partition. Let V1,V2 be a partiion such that w(V1,V2) = k. Observe that v must be in one of V1 or V2, so without loss of generality suppose v in V1. The edges in w(V1,V2) will be exactly those between v and the other elements of V1. Let S = {i | v_i in V1}. Then S is a solution to partition since w(V1,V2) = sum_{i in S} xi = (x1 + ... + xn)/2 by the fact that V1,V2 is a SIP solution.
You can prove this is optimal using the greedy choice and optimal substructure methodology. Just pick one vertex v in V, and put it's neighbor v' in the cover. You can prove that there exists some optimal solution with v'. Take an arbitrary optimal cover. If it does not contain v' then it must contain v since the edges (v,v') must be covered. So you can move the vertex in the optimal cover from v to v' and it will still be a cover. It is also easy to prove that the optimal substructure property holds.