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 '12 at 8:39
  • 2
    $\begingroup$ Edited for clarity. $\endgroup$ – JeffE Sep 12 '12 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 '12 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 '12 at 19:34

Your Answer

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

Browse other questions tagged or ask your own question.