Question

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 NP-complete in lecture is N'P-complete. For purposes of this assignment, use only those problems 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 C G such that for every vE R, vET 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.

Answer 1