1. The STEINER TREE problem is as follows. Given an undirected graph G = (V,E) with nonnegative edge costs and whose vertices are partitioned into two sets, R and S, find a tree T S G such that for every v E R, v ET with total cost at most C. That is, the tree that contains every vertex in R (and possibly some in S) with a total edge cost of at most C. Prove that this problem is N'P-complete Note that things like searching for solutions online is still prohibited. In order to prove a problem is NP-complete, you must: . Show that the problem is in NP . A reduction in the correct direction. Reductions in the wrong direction will considerably reduce the credit you can get for a problem . An explanation for why your reduction has no false positives An explanation for why your reduction has no false negatives. You may assume that any problem shown to be N'P-complete in lecture is NP-complete. For purposes of this assignment, use only those problems