Arc-disjoint in-trees in directed graphs (Q987553): Difference between revisions

The authors generalize an old theorem of \textit{J. Edmonds} [Combinatorial algorithms. R. Rustin eds. Courant computer science symposium 9: January 24--25, 1972 (1972; Zbl 0366.68023); pp. 91--96], and a result from \textit{A. Schrijver} [Algorithms and Combinatorics 24, Berlin, Springer (2003; Zbl 1041.90001)]. The first states that given a directed graph \(D=(V, A)\), with a specified vertex \(s \in V\), there exist \(k\) arc-disjoint in-trees rooted at \(s\) each of which spans \(V\) if and only if there are \(k\) arc-disjoint directed paths from any \(v \in V \setminus s\) and \(s\). In the other a vertex set \(S=\{s_1, \dots, s_d \}\) is specified together with a function \(f: S \rightarrow N\). A more or less straightforward generalization gives a necessary and sufficient condition for the existence of arc-disjoint in-trees \(T_{i, 1}, \dots, T_{i, f(s_i)}\), where \(T_{i, j}\) is rooted at \(s_i\), and each \(T_{i, j}\) spans \(V\). The main theorem of this paper generalizes this statement even more to the case where a \(T_{i, j}\) spans only a set \(V_i\), namely the set from which the vertex \(s_i\) is reachable.