# An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points (in my application, the distances are Manhattan/$L_1$).

For example, given the locations of US cities, we would find an MST that connects to one city from every state.

If helpful, we could additionally assume that the local density of the pointset is upper-bounded (the points can't be clustered too closely). Points of the same color will generally come in groups (can even assume that each color corresponds to a connected region).

A straightforward heuristic would average locations of points of each color, build an MST for those "centers", and then look for shortcuts. Is there something better ?

Points of interest: a proof of NP-hardness (e.g., by reduction from min Steiner tree), an approximation algorithm (e.g., by reduction to $k$-MST), an effective heuristic, etc.

-
If I understood your question correctly, it can be stated formally as: given a set of colors $\{ C_1,...,C_k \}$ and a set of points $\{p_1,...,p_n\}$ each labeled with a color and $n \ge k$, choose a subset of size $k$ of points each with a different color, such that the resulting MST has the minimum sum of length of edges. –  Mohsen May 25 '12 at 11:16
If so, the problem can be solved in polynomial time indeed. Let $|C_i|$ show the number of points with color $C_i$. Since we have $|C_1|...|C_k|$ subsets of the points with the desired property and MST can be solved in poly-time, the whole search space can be easily explored in poly-time. –  Mohsen May 25 '12 at 11:16
The interpretation seems correct, but I don't follow your poly-time argument. Let's say there are exactly two points of each color. Then $\forall i~|C_i|=2$, so you get $2^{n/2}$ possible configurations to check by brute force. –  Igor Markov May 29 '12 at 6:53
If $n$ is your variable and $k$ is a constant, them my argument is correct. Otherwise, yours is correct. In the above example (US cities), it looks to me that the number of colors ($k$) is fixed. –  Mohsen May 29 '12 at 8:34