# Minimum vertex-weight directed spanning tree where the weight function depends on the tree

Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$.

The weight function assigns a non-negative weight to each node, which depends on the node's ancestors in $T$. Specifically, for some fixed sets of nodes $S_1, S_2, \dots, S_k \subseteq V$, the weight of node $v$ is the number of sets $S_i$ that contain $v$ and all its ancestors in $T$.

Any suggestion how to approach this problem?

• Do you mean ancestors?
– Joe
Sep 10, 2012 at 8:39
• Edited for clarity. Sep 12, 2012 at 22:32
• Interesting. Can you give some information about the background/motivation? Maybe there is another way to solve your problem. What are your constraints, e.g. runtime? The naive algorithm just tries all possible trees. The new formulation seems to imply that $T$ has to have directed paths from $r$ to all leaves (i.e. you can only use edges of $G$ in their original orientation); is that intended? Also, what have you tried?
– Raphael
Sep 13, 2012 at 6:24
• Are there any guarantees on how the function changes depending on the ancestors? In other words, do you know that it can only increase with more ancestors or some such? If so, a variant of Djikstra's might work or possibly dynamic programming.
– SamM
Sep 13, 2012 at 19:34