<p>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?</p>

CC BY-SA 4.0
2020-03-12T22:55:22.427Z
Thanks! I change the description.
Yuliang Li
CC BY-SA 4.0
2020-03-12T23:23:01.713Z
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.
Yuliang Li
CC BY-SA 4.0
2020-03-14T01:14:09.847Z
The additional restriction seems difficult to enforce. Perhaps the problem is NP-Complete but one has to spend some time to find a reduction.
Chandra Chekuri
<graph-theory><graph-algorithms><search-problem><spanning-tree>
Variation of edge-disjoint spanning trees
Yuliang Li
# Variation of edge-disjoint spanning trees

(Asked by: username_0 on 2020-03-12)

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?

**Tags:** graph-theory, graph-algorithms, search-problem, spanning-tree
> **Comments:**
> **username_0**: Thanks! I change the description.  
> **username_0**: 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.  
> **username_1**: The additional restriction seems difficult to enforce. Perhaps the problem is NP-Complete but one has to spend some time to find a reduction.  

---

## 0 answers

