1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Dec 5 '16 at 11:29
  • $\begingroup$ 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). $\endgroup$ – Saeed Dec 5 '16 at 11:49
  • $\begingroup$ 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? $\endgroup$ – Neal Young Mar 22 '17 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.