# On Finding Optimal (Dynamic) Arborescences
## 2 Optimal Arborescences
### Edmonds' Algorithm
#### 2.1.3 Illustrative Example  
Let us consider the graph in Figure 0(a). Let the input graph be denoted by \(G_{0}\). In Figure 0(b), the minimum weight incident edges in every vertex of \(G_{0}\) are colored in red; those edges are added: \(E_{0}=\{(2,0),(3,1),(3,2),(2,4),(5,3),(4,6),(6,7)\}\). The green edges in Figure 0(c) form a cycle and are added to \(Q_{0}=\{(3,2),(2,4),(4,5),(5,3)\}\). The cycle \(Q_{0}\) must then be contracted. The maximum weight edge in \(Q_{0}\) is the edge \((4,5)\), and \(\sigma_{Q_{0}}=9\). In Figure 1(a), it is shown the contracted version of \(G_{0}\), which is named \(G_{1}\), with the reduced costs already computed. In Figure 1(b), the minimum weight incident edges are highlighted in red, and they are added to \(E_{1}=\{(C,0),(C,1),(C,6),(7,C),(6,7)\}\). In Figure 1(c), the cycle \(Q_{1}=\{(C,6),(6,7),(7,C)\}\) is marked in green, and it will be contracted. The maximum weight edge of \(Q_{1}\) is edge \((C,6)\), and \(\sigma_{Q_{1}}=12\). Figure 1: Identification of the cycle \(Q_{0}\) in \(G_{0}\). (**a**) Input weighted directed graph. (**b**) Minimum weight incident edges in every vertex of graph \(G_{0}\), which are colored in red. (**c**) Cycle in \(G_{0}\) colored in green. Figure 2: _Cont._  
The contracted version of \(G_{1}\), which is named \(G_{2}\), is presented in Figure 3a. The minimum weight incident edges in every vertex of \(G_{2}\) are marked in red in Figure 3b, and they are added to \(E_{2}=\{(0,C^{\prime}),(C^{\prime},0),(C^{\prime},1)\}\). \(E_{2}\) has a cycle, \(Q_{2}=\{(0,C^{\prime}),(C^{\prime},0)\}\), that is colored in green in Figure 3c. This cycle must be also contracted. The maximum weight edge of \(Q_{2}\) is edge \((0,C^{\prime})\), and \(\sigma_{Q_{2}}=15\). Since \(E_{2}\) contains a cycle, a contraction is required, and we obtain the graph \(G_{3}\) in Figure 4a. The minimum incident edges in \(G_{3}\) are marked in red in Figure 4b, and they are added to \(E_{3}=\{(1,C^{\prime\prime}),(C^{\prime\prime},1)\}\). Note that \(E_{3}\) contains another cycle: \(Q_{3}=\{(1,C^{\prime\prime}),(C^{\prime\prime},1)\}\). The maximum weight edge present in \(Q_{3}\) is \((1,C^{\prime\prime})\), and \(\sigma_{Q_{3}}=16\). A final contraction of cycle \(Q_{3}\) is required, thus leading to \(G_{4}\) with a single vertex, which is shown in Figure 4d. In this last iteration, we have \(E_{4}=\emptyset\) and \(Q_{4}=\emptyset\), thereby ending the contraction phase. The expansion phase expands the cycles formed in reverse order by kicking out one edge per cycle. The removed edges are presented as dashed edges. Let \(H=E_{4}\), and let the  
Figure 4: Contraction of \(Q_{2}\), identification of \(Q_{3}\), and final graph \(G_{4}\) after \(Q_{3}\) contraction. (**a**) Contracted version of \(G_{2}\), which is named \(G_{3}\). (**b**) Minimum weight incident edges in \(G_{3}\). (**c**) Cycle \(Q_{3}\) in \(G_{3}\) colored in green. (**d**) \(G_{4}\). Figure 3: Contraction of cycle \(Q_{1}\) and identification of cycle \(Q_{2}\). (**a**) Contracted version of \(G_{1}\), which is named \(G_{2}\). (**b**) Minimum weight incident edges in \(G_{2}\). (**c**) Cycle in \(G_{2}\) colored in green. Figure 2: Contraction of cycle \(Q_{0}\) and identification of cycle \(Q_{1}\). (**a**) Contracted version of graph \(G_{0}\), which is named \(G_{1}\). (**b**) Minimum weight incident edges in every vertex of graph \(G_{1}\). (**c**) Cycle \(Q_{1}\) in graph \(G_{1}\) colored in green. decrement be \(i\). Vertex \(C^{\prime\prime\prime}\) is a root of \(H\), since there is no edge directed towards \(C^{\prime\prime\prime}\). In this case, every edge of \(Q_{3}\) is added to \(H\) except the maximum weight edge of the cycle, as shown in Figure 5a. In iteration \(i=2\), note that \(H=\{(C^{\prime},1)\}\), and vertex \(C^{\prime}\) is a root; therefore, every edge from \(Q_{2}\) must be added to \(H\) except the maximum weight edge \((C^{\prime},0)\). In the next iteration, \(i=1\), vertex \(C\) is not a root of \(H\), since edge \((0,C)\in H\).