Let G $=($V$,$ E$)$ be a graph with nonnegative edge costs. S and R are two

disjoint subsets of V $,$ where S is a set of senders and R is a set of receivers. The problem is to find a minimum cost subgraph of G that has a path connecting each receiver to a sender $($any sender

suffices$).$

$(1)$ If S $$ R $=$ V $,$ show that this problem is in P$.$

$(2)$ If S $$ R $=$ V $,$ show that this problem is NP$-$hard. Give a $2-$approximation algorithm for this case.

The hint for proving that the problem is NP$-$hard is to add a new vertex connected to each sender by a zero cost edge and transform the problem to the Steiner tree problem.

Given an undirected graph G $=($V$,$ E$)$ with nonnegative edge costs and whose vertices are partitioned into two sets, required and Steiner, a Steiner tree is a tree in G that spans the required set. The Steiner tree problem is to find a minimum cost tree in G that contains all the required vertices and any subset of the Steiner vertices. The decision form of the Steiner tree problem is defined as follows: given an undirected graph G $=($V$,$ E$),$ a subset of the vertices R $$ V $($terminal nodes$)$ and a number k in N $,$ is there a subtree of G that includes all the vertices of R $($i$.$e$.$ a spanning tree for R$)$ and that has cost at most k$?$ This problem is proven NP$-$complete.