Edmonds' algorithm

Algorithm

Description

The algorithm takes as input a directed graph ${\displaystyle D=⟨V,E⟩}$ where ${\displaystyle V}$ is the set of nodes and ${\displaystyle E}$ is the set of directed edges, a distinguished vertex ${\displaystyle r\in V}$ called the root, and a real-valued weight ${\displaystyle w(e)}$ for each edge ${\displaystyle e\in E}$. It returns a spanning arborescence ${\displaystyle A}$ rooted at ${\displaystyle r}$ of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, ${\displaystyle w(A)=\sum _{e\in A}w(e)}$.

The algorithm has a recursive description. Let ${\displaystyle f(D,r,w)}$ denote the function which returns a spanning arborescence rooted at ${\displaystyle r}$ of minimum weight. We first remove any edge from ${\displaystyle E}$ whose destination is ${\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 ${\displaystyle v}$ other than the root, find the edge incoming to ${\displaystyle v}$ of lowest weight (with ties broken arbitrarily). Denote the source of this edge by ${\displaystyle \pi (v)}$. If the set of edges ${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}$ does not contain any cycles, then ${\displaystyle f(D,r,w)=P}$.

Otherwise, ${\displaystyle P}$ contains at least one cycle. Arbitrarily choose one of these cycles and call it ${\displaystyle C}$. We now define a new weighted directed graph ${\displaystyle D^{\mathrm{\prime }}=⟨V^{\mathrm{\prime }},E^{\mathrm{\prime }}⟩}$ in which the cycle ${\displaystyle C}$ is "contracted" into one node as follows:

The nodes of ${\displaystyle V^{\mathrm{\prime }}}$ are the nodes of ${\displaystyle V}$ not in ${\displaystyle C}$ plus a new node denoted ${\displaystyle v_C}$.

• If ${\displaystyle (u,v)}$ is an edge in ${\displaystyle E}$ with ${\displaystyle u\notin C}$ and ${\displaystyle v\in C}$ (an edge coming into the cycle), then include in ${\displaystyle E^{\mathrm{\prime }}}$ a new edge ${\displaystyle e=(u,v_C)}$, and define ${\displaystyle w^{\mathrm{\prime }}(e)=w(u,v)-w(\pi (v),v)}$.
• If ${\displaystyle (u,v)}$ is an edge in ${\displaystyle E}$ with ${\displaystyle u\in C}$ and ${\displaystyle v\notin C}$ (an edge going away from the cycle), then include in ${\displaystyle E^{\mathrm{\prime }}}$ a new edge ${\displaystyle e=(v_C,v)}$, and define ${\displaystyle w^{\mathrm{\prime }}(e)=w(u,v)}$.
• If ${\displaystyle (u,v)}$ is an edge in ${\displaystyle E}$ with ${\displaystyle u\notin C}$ and ${\displaystyle v\notin C}$ (an edge unrelated to the cycle), then include in ${\displaystyle E^{\mathrm{\prime }}}$ a new edge ${\displaystyle e=(u,v)}$, and define ${\displaystyle w^{\mathrm{\prime }}(e)=w(u,v)}$.

For each edge in ${\displaystyle E^{\mathrm{\prime }}}$, we remember which edge in ${\displaystyle E}$ it corresponds to.

Now find a minimum spanning arborescence ${\displaystyle A^{\mathrm{\prime }}}$ of ${\displaystyle D^{\mathrm{\prime }}}$ using a call to ${\displaystyle f(D^{\mathrm{\prime }},r,w^{\mathrm{\prime }})}$. Since ${\displaystyle A^{\mathrm{\prime }}}$ is a spanning arborescence, each vertex has exactly one incoming edge. Let ${\displaystyle (u,v_C)}$ be the unique incoming edge to ${\displaystyle v_C}$ in ${\displaystyle A^{\mathrm{\prime }}}$. This edge corresponds to an edge ${\displaystyle (u,v)\in E}$ with ${\displaystyle v\in C}$. Remove the edge ${\displaystyle (\pi (v),v)}$ from ${\displaystyle C}$, breaking the cycle. Mark each remaining edge in ${\displaystyle C}$. For each edge in ${\displaystyle A^{\mathrm{\prime }}}$, mark its corresponding edge in ${\displaystyle E}$. Now we define ${\displaystyle f(D,r,w)}$ to be the set of marked edges, which form a minimum spanning arborescence.

Observe that ${\displaystyle f(D,r,w)}$ is defined in terms of ${\displaystyle f(D^{\mathrm{\prime }},r,w^{\mathrm{\prime }})}$, with ${\displaystyle D^{\mathrm{\prime }}}$ having strictly fewer vertices than ${\displaystyle D}$. Finding ${\displaystyle f(D,r,w)}$ for a single-vertex graph is trivial (it is just ${\displaystyle D}$ itself), so the recursive algorithm is guaranteed to terminate.