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.

Improve this question
$\endgroup$
3
  • $\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, 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

0

Reset to default

Your Answer

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