An out‐branching
(in‐branching
) in a digraph
is a connected spanning subdigraph of
in which every vertex except the vertex
, called the root, has in‐degree (out‐degree) one. It is well known that there exists a polynomial algorithm for deciding whether a given digraph has
arc‐disjoint out‐branchings with prescribed roots (
is part...