social network analysis - relations between people with weights
First a few comments/questions about your approach:

Why do you think your problem has anything to do with minimum spanning trees? I fail to see the connection.
Why is your graph directed when the original problem seems to state that the &quot;know eachother&quot; relation is symmetric? (if A knows B then B knows A)
For your &quot;greedy post-processing&quot; can you do better than looking at all possible  subsets of D? In other words, how does your MST help you compute the correct subset?

Then to answer your question:
If I understood you correctly, the problem you want to solve is a weighted version of dominating set. It is NP-Hard and thus unlikely to be solvable efficiently in the worst case when the number of people increases.
By googling &quot;minimum weight dominating set&quot; you will however find approximation algorithms, heuristics or &quot;practically efficient&quot; algorithms which might do the trick if the number of people in S is not too large (or the specific instance happens to be nice enough). I'm not sure how well they would perform for your considered graph size.
Alternatively, if the number of people in S is really not large (say fewer than 25) then you might consider simply brute-forcing through every possible subset of S.