In a directed graph, I want to find 2 edge-disjoint spanning trees (arborescence), with the extra restrictions that edges in the 1st tree are not forward arcs in the 2nd tree. Are there existing algorithms I can use, or efficient modifications to existing algorithms?

  • $\begingroup$ Thanks! I change the description. $\endgroup$ – Yuliang Li Mar 12 '20 at 22:55
  • $\begingroup$ I updated the description. Both trees are arborescence. Sorry for the confusion. I am not a CS theorist, so I might have used some amateur words. $\endgroup$ – Yuliang Li Mar 12 '20 at 23:23
  • $\begingroup$ The additional restriction seems difficult to enforce. Perhaps the problem is NP-Complete but one has to spend some time to find a reduction. $\endgroup$ – Chandra Chekuri Mar 14 '20 at 1:14

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.