I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N[V']=V$, $∀v'∈V '[∃r∈R ($path($r', v'$)$)]$ that minimizes the sum of vertex weights in $V'$. Note the path must contain only vertices in $V'$.

In other words, all roots must be in $V'$, the closed neighborhood of $V'$ must include all vertices in the original graph and every vertex in $V'$ needs to have a path to a root.

I have constructed a naive algorithm that takes the powerset of $V$ and checks for each subset if it satisfies the 3 constraints. The first constraint is trivial, the second requires the algorithm to compare the union of $V'$ with $V$, and the third one is done by using DFS (only adding vertices to discovered if they are in $V'$.

I was thinking I could convert the vertex-weighted undirected graph to a edge-weighted directed graph and then run Chu-liu/Edmonds' algorithm to find a minimal spanning arborescence. I tried converting the graph by adding $v'$ for each $v$ in $V$, with an edge $(v,v')$ with the vertex weight. All outgoing vertices from $v$ will now be outgoing from $v'$. The problem is that these auxiliary vertices don't need to be included in the MSA, but Chu-liu/Edmonds' algorithm will include them.

Actual question: Is there a better way to convert the graph, so that I can use this approach, or should I go for another (maybe even easier) approach?

  • 1
    $\begingroup$ Can you define what the notation $N[V']$ represents? What does the notation $R(\textsf{path}(r',v'))$ represent? $\endgroup$ – D.W. Nov 22 '20 at 22:20
  • $\begingroup$ $N[V']$ denotes the closed neighborhood of $V'$, $∃r∈R()$ denotes: there exists a root, such that, and path($r',v'$) denotes there exists a path between $r'$ and $v'$ (in this case using only vertices in $V'$ $\endgroup$ – J. Vroegindeweij Nov 23 '20 at 6:15
  • $\begingroup$ Please edit the question so it contains that information. We ask that questions be self-contained, so people don't need to read the comments to understand what you are asking. Then, you can flag the comments as 'no longer needed. $\endgroup$ – D.W. Nov 23 '20 at 6:51

Without loss of generality we can assume the graph is connected. (If not, decompose it into connected components, and solve the problem separately on each component.) Since it is connected, every vertex has a path to every other, so we can ignore the requirement to have a path to a root.

So your problem becomes: given $R$, find a minimum dominating set $V'$ that contains $R$. This is NP-complete; indeed, the special case where $R=\emptyset$ is the standard dominating set problem, which is NP-complete, so your problem is, too.

If you need to solve your problem in practice, you could apply any of the standard techniques for dominating set or set cover. For instance, you could use an approximation algorithm or greedy heuristic to get an approximate solution; or you could use a SAT solver or ILP solver to get an exact solution and hope that it terminates in a reasonable amount of time on your specific problem instances.

  • $\begingroup$ I didn't know about the dominating set problem, but it seems to suit my needs perfectly. More specifically, after some research i found that my problem is a minimum weighted connected dominating set problem. This includes the second and third constraint, so indeed, the problem is finding a solution that contains R. $\endgroup$ – J. Vroegindeweij Nov 23 '20 at 6:19

Your Answer

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

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