<p>I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is maximized. Has this problem been studied before? It is submodular. </p>

CC BY-SA 3.0
2016-12-05T11:29:49.243Z
I am not sure this particular problem has been studied, but general results on maximizing monotone submodular functions subject to a cardinality constraints should apply.
Sasho Nikolov
CC BY-SA 3.0
2016-12-05T11:49:50.350Z
I think it is already np-hard for the case where we just have weights on edges. Do you know anything about this particular case (I'm not sure if I thought correctly, but if there are some other results, I don't need to write it).
Saeed
CC BY-SA 3.0
2017-03-22T11:09:47.143Z
What exactly do you mean by "the weight of their minimum spanning tree"?  Do you mean the minimum-weight spanning tree of the subgraph they induce, or the minimum-weight Steiner tree with them as terminals?
Neal Young
<ds.algorithms><graph-theory><approximation-algorithms><tree><submodularity>
Maximize the weight of MST + sum of vertex weights
Johnson
# Maximize the weight of MST + sum of vertex weights

(Asked by: username_0 on 2016-12-05)

I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is maximized. Has this problem been studied before? It is submodular.

**Tags:** ds.algorithms, graph-theory, approximation-algorithms, tree, submodularity
> **Comments:**
> **username_1**: I am not sure this particular problem has been studied, but general results on maximizing monotone submodular functions subject to a cardinality constraints should apply.  
> **username_2**: I think it is already np-hard for the case where we just have weights on edges. Do you know anything about this particular case (I'm not sure if I thought correctly, but if there are some other results, I don't need to write it).  
> **username_3**: What exactly do you mean by "the weight of their minimum spanning tree"?  Do you mean the minimum-weight spanning tree of the subgraph they induce, or the minimum-weight Steiner tree with them as terminals?  

---

## 0 answers

