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

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?

• Can you define what the notation $N[V']$ represents? What does the notation $R(\textsf{path}(r',v'))$ represent? – D.W. Nov 22 at 22:20
• $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'$ – J. Vroegindeweij Nov 23 at 6:15
• 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. – D.W. Nov 23 at 6:51

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.