Representing graph metrics with fewest edges

We are given a graph with edge weights, that represents the metric on the vertices in which the distance between two vertices is the total weight of the lowest-weight path between them. Consider the prob-lem of representing this metric using as few edges as possible, provided that new "Steiner" vertices (and edges incident on them) can be added. The compression factor achieved is the ratio k between the number of edges in the original graph and the number of edges in the compressed graph. We obtain approximation algorithms for unit weight graphs that replace cliques with stars in cases where the cliques so compressed are disjoint, or when only a constant number of the cliques compressed meet at any vertex. We also show that the general unit weight problem is essentially as hard to approximate as graph coloring and maximum clique