# Maximize the weight of MST + sum of vertex weights

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.

• 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 Dec 5 '16 at 11:29
• 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 Dec 5 '16 at 11:49
• 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 Mar 22 '17 at 11:09