Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints

Question

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?

Answer 1

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.