Has this problem been studied before?
Given a metric undirected graph G (edge lengths satisfy triangle inequality), find a set S of vertices such that MST(G[S]) is maximized, where MST(G[S]) is the minimum spanning tree of the subgraph induced by S. Has this problem been studied before? Is it NP-hard? Thanks a lot.
It's NP-complete by a reduction from vertex cover.
Let $G$ be a graph in which an optimal vertex cover is hard to find. Make a new graph $H$ with twice as many vertices, by attaching a new degree-one vertex to each vertex of $G$. Turn $H$ into a metric space by making the distance between adjacent vertices equal to $1$ and the distance between non-adjacent vertices equal to $2$. For this metric space, the weight of a minimum spanning tree of an induced subgraph equals the number of vertices plus the number of connected components of the subgraph minus one.
We can assume that the subgraph with the heaviest MST includes all of the degree-one vertices, because adding one of these vertices to a subset can never decrease the number of components. So the vertices that were removed to form the subgraph are a subset of $G$. We can assume also that these removed vertices form a vertex cover of $G$. For, if some other induced subgraph is formed by removing vertices that do not form a vertex cover, and $uv$ is an edge that is not covered, then removing $v$ leads to an induced subgraph that is at least as good: it has one less vertex but one more connected component, created by the degree-one vertex of $H$ that was attached to $v$.
So the optimal subgraph of $H$ is formed by removing a vertex cover from $G$. Such a subgraph will have exactly $n$ components (one for each degree-one vertex added to $H$, either by itself or connected to a vertex of $G$), and a number of vertices equal to $2n-k$ where $n=|V(G)|$ and $k$ is the size of the cover. Thus, the weight of its MST will be $3n-k+1$. To maximize this, we must minimize $k$.
