3
$\begingroup$

I asked this question on datascience.stackexchange but they directed me here.

I have a social network represented as a set of people $S$ and individual weights for each of person (weight is the cost of person). I also have defined relationships between these people (whether people know each other or not). I must find such a subset $D$, such that every person in this subset either belongs to the set $D$ or knows someone from the set $D$ directly.

There will be a lot of such subsets. I want the subset whose sum of weights of people is the smallest.

Let's see example:

D = {(John(7), Adam(15), Viktor(6), Bob(2)} and connections are John - Adam - Viktor - Bob. Solutions are Adam,Bob(17) OR John,Victor(13) OR Adam,Victor(21) OR John,Bob(9). The best is the last one - John,Bob(9).

I thought to create a directed graph where:

  • Each vertex represents person
  • Each vertex has a weight assigned to it
  • Edges between vertices indicate whether the people know each other or not

I imagine this as a minimum spanning tree on directed graphs problem. I found Chu-Liu/Edmond's algorithm, I know that this algorithm works for edge-weighted graphs and I have vertices-weighted, so I just set the edge weights to what are the weights of the vertices at the end of the edge. But this is not optimal solution. I don't need direct connections between people in the set $D$.

So after I have result from that algorithm, I can apply on it some greedy algorithm, which will go recursively over each element and check how removing it from the subset $D$ will affect the structure - when the sum of the weights will be minimal and will ensure that no element falls out of set $D$ (check below).

Refer to an example, my MST result will be John,Adam,Victor,Bob(27). Best solution is John,Bob(9). Interesting bad solution is Viktor,Bob(8) - the sum is minimal, unfortunately John will fall out of the $D$ subset.

Also I assume that:

  • cost of a person doesn't correlate with their degree in the network (numbers of acquaintances)
  • the maximum number of people and acquaintances (vertices and edges) is about 400

Is my way to solve this problem is good? Do you suggest any other solutions for that?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

This is the minimum weight dominating set problem. You can solve it via integer linear programming as follows. For node $i \in S$, let $w_i$ be the weight and let $N_i \subseteq S$ be the set of neighbors. Let binary decision variable $x_i$ indicate whether $i \in D$. The problem is to minimize $\sum_{i \in S} w_i x_i$ subject to $$x_i + \sum_{j \in N_i} x_j \ge 1 \quad \text{for $i \in S$}$$

Improve this answer
$\endgroup$
4
  • $\begingroup$ ... also known as the hitting set problem and set covering problem, because, of course, you can never have too many names for the same thing. :-) $\endgroup$
    – prubin ♦
    Aug 9, 2020 at 17:38
  • $\begingroup$ Yes, this is a special case of those two more general equivalent problems. $\endgroup$
    – RobPratt
    Aug 9, 2020 at 17:44
  • $\begingroup$ @RobPratt, thanks for answer. You wrote it as if it is something simple, but unfortunately that doesn't tell me much. Is there some algorithm or implementation that solves minimum weight dominating set problem? $\endgroup$
    – czaduu
    Aug 10, 2020 at 2:24
  • 1
    $\begingroup$ There are numerous integer linear programming solvers available, both commercial and free. $\endgroup$
    – RobPratt
    Aug 10, 2020 at 2:52

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.