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?

  • 2
    $\begingroup$ Do you mean ancestors? $\endgroup$
    – Joe
    Sep 10, 2012 at 8:39
  • 2
    $\begingroup$ Edited for clarity. $\endgroup$
    – JeffE
    Sep 12, 2012 at 22:32
  • $\begingroup$ 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? $\endgroup$
    – Raphael
    Sep 13, 2012 at 6:24
  • $\begingroup$ 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. $\endgroup$
    – SamM
    Sep 13, 2012 at 19:34


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.