Edmonds' algorithm

In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching).It is the directed analog of the minimum spanning tree problem.The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967). In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching).It is the directed analog of the minimum spanning tree problem.The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967). The algorithm takes as input a directed graph D = ⟨ V , E ⟩ {displaystyle D=langle V,E angle } where V {displaystyle V} is the set of nodes and E {displaystyle E} is the set of directed edges, a distinguished vertex r ∈ V {displaystyle rin V} called the root, and a real-valued weight w ( e ) {displaystyle w(e)} for each edge e ∈ E {displaystyle ein E} .It returns a spanning arborescence A {displaystyle A} rooted at r {displaystyle r} of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, w ( A ) = ∑ e ∈ A w ( e ) {displaystyle w(A)=sum _{ein A}{w(e)}} . The algorithm has a recursive description.Let f ( D , r , w ) {displaystyle f(D,r,w)} denote the function which returns a spanning arborescence rooted at r {displaystyle r} of minimum weight.We first remove any edge from E {displaystyle E} whose destination is r {displaystyle r} .We may also replace any set of parallel edges (edges between the same pair of vertices in the same direction) by a single edge with weight equal to the minimum of the weights of these parallel edges. Now, for each node v {displaystyle v} other than the root, find the edge incoming to v {displaystyle v} of lowest weight (with ties broken arbitrarily).Denote the source of this edge by π ( v ) {displaystyle pi (v)} .If the set of edges P = { ( π ( v ) , v ) ∣ v ∈ V ∖ { r } } {displaystyle P={(pi (v),v)mid vin Vsetminus {r}}} does not contain any cycles, then f ( D , r , w ) = P {displaystyle f(D,r,w)=P} . Otherwise, P {displaystyle P} contains at least one cycle.Arbitrarily choose one of these cycles and call it C {displaystyle C} .We now define a new weighted directed graph D ′ = ⟨ V ′ , E ′ ⟩ {displaystyle D^{prime }=langle V^{prime },E^{prime } angle } in which the cycle C {displaystyle C} is 'contracted' into one node as follows: The nodes of V ′ {displaystyle V^{prime }} are the nodes of V {displaystyle V} not in C {displaystyle C} plus a new node denoted v C {displaystyle v_{C}} . For each edge in E ′ {displaystyle E^{prime }} , we remember which edge in E {displaystyle E} it corresponds to. Now find a minimum spanning arborescence A ′ {displaystyle A^{prime }} of D ′ {displaystyle D^{prime }} using a call to f ( D ′ , r , w ′ ) {displaystyle f(D^{prime },r,w^{prime })} .Since A ′ {displaystyle A^{prime }} is a spanning arborescence, each vertex has exactly one incoming edge.Let ( u , v C ) {displaystyle (u,v_{C})} be the unique incoming edge to v C {displaystyle v_{C}} in A ′ {displaystyle A^{prime }} .This edge corresponds to an edge ( u , v ) ∈ E {displaystyle (u,v)in E} with v ∈ C {displaystyle vin C} .Remove the edge ( π ( v ) , v ) {displaystyle (pi (v),v)} from C {displaystyle C} , breaking the cycle.Mark each remaining edge in C {displaystyle C} .For each edge in A ′ {displaystyle A^{prime }} , mark its corresponding edge in E {displaystyle E} .Now we define f ( D , r , w ) {displaystyle f(D,r,w)} to be the set of marked edges, which form a minimum spanning arborescence. Observe that f ( D , r , w ) {displaystyle f(D,r,w)} is defined in terms of f ( D ′ , r , w ′ ) {displaystyle f(D^{prime },r,w^{prime })} , with D ′ {displaystyle D^{prime }} having strictly fewer vertices than D {displaystyle D} . Finding f ( D , r , w ) {displaystyle f(D,r,w)} for a single-vertex graph is trivial (it is just D {displaystyle D} itself), so the recursive algorithm is guaranteed to terminate.