<p>It's NP-complete by a reduction from vertex cover.</p>

<p>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.</p>

<p>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$.</p>

<p>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$.</p>

CC BY-SA 3.0
2015-12-23T17:03:00.137Z
2015-12-23T17:03:00.137Z
David Eppstein
<p>Has this problem been studied before?</p>

<p>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.</p>

CC BY-SA 3.0
2013-08-06T15:17:59.200Z
Is there a straightforward usage of this subgraph in theory or practice?
Saeed
CC BY-SA 3.0
2013-08-06T16:32:29.053Z
If you remove the metric condition, is it easy to prove that the problem is NP-hard?
Igor Shinkar
CC BY-SA 3.0
2017-03-18T15:37:16.677Z
Taking $S$ to contain all vertices gives a $0.5$-approximation.
Neal Young
<ds.algorithms><graph-algorithms><np-hardness><approximation-algorithms>
maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph
jian
# maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph

(Asked by: username_0 on 2013-08-05)

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.

**Tags:** ds.algorithms, graph-algorithms, np-hardness, approximation-algorithms
> **Comments:**
> **username_1**: Is there a straightforward usage of this subgraph in theory or practice?  
> **username_2**: If you remove the metric condition, is it easy to prove that the problem is NP-hard?  
> **username_3**: Taking $S$ to contain all vertices gives a $0.5$-approximation.  

---

## 1 answers

### Answer by username_4 on 2015-12-23. Score: 4 | Accepted answer

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$.


---

