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.

  • $\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$ Dec 5, 2016 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, 2016 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, 2017 at 11:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.