The fault-tolerant version of the k-center problem with triangle inequality has an additional input k which specifies the number of centers that each vertex must be connected to. In other words, we assume that up to 1 centers might be closed, and so the fault-tolerant cost for a vertex is its distance to its th closest center. The problem is to pick k centers so that the maximum fault-tolerant cost of a vertex is minimized. A set S V in an undirected graph H = (V, E) is an - dominating set if each vertex v V is adjacent to at least vertices in S (we consider a vertex to be adjacent to itself). Let dom(H) denote the size of a minimum cardinality -dominating set in H.

(a) Let I be an independent set in H2 . Show that |I| dom(H).

(b) Give a factor 3 approximation algorithm for the fault-tolerant kcenter problem (Hint: Compute a maximal independent set Mi in G2 i , for 1 i m. Find the smallest index i such that |Mi | b k c, and moreover, the degree of each vertex of Mi in Gi is 1.)