Directed Steiner tree packing and directed tree connectivity

For a digraph $D=(V(D),A(D))$, and a set $S\subseteq V(D)$ with $r\in S$ and $\mathrm{\mid }S\mathrm{\mid }\ge 2$, an $(S,r)$-tree is an out-tree $T$ rooted at $r$ with $S\subseteq V(T)$\mathrm{.}Two$(S, r)$-trees$T_1$and$T_2$aresaidtobearc-disjointif$A(T_1)\cap A(T_2)=\emptyset$\mathrm{.}Twoarc-disjoint$(S, r)$-trees$T_1$and$T_2$aresaidtobeinternallydisjointif$V(T_1)\cap V(T_2)=S$\mathrm{.}Let$\kappa_{S,r}(D)$and$\lambda_{S,r}(D)$ be the maximum number of internally disjoint and arc-disjoint $(S,r)$-trees in $D$, respectively. The generalized $k$-vertex-strong connectivity of $D$ is defined as $${\kappa }_k(D)=\min \{{\kappa }_{S,r}(D)\mid S\subset V(D),\mathrm{\mid }S\mathrm{\mid }=k,r\in S\}\mathrm{.}$$ Similarly, the generalized $k$-arc-strong connectivity of $D$ is defined as $${\lambda }_k(D)=\min \{{\lambda }_{S,r}(D)\mid S\subset V(D),\mathrm{\mid }S\mathrm{\mid }=k,r\in S\}\mathrm{.}$$ The generalized $k$-vertex-strong connectivity and generalized $k$-arc-strong connectivity are also called directed tree connectivity which extends the well-established tree connectivity on undirected graphs to directed graphs and could be seen as a generalization of classical connectivity of digraphs. In this paper, we completely determine the complexity for both $\kappa_{S, r}(D)$and$\lambda_{S, r}(D)$ on general digraphs, symmetric digraphs and Eulerian digraphs. In particular, among our results, we prove and use the NP-completeness of 2-linkage problem restricted to Eulerian digraphs. We also give sharp bounds and characterizations for the two parameters ${\kappa }_k(D)$ and ${\lambda }_k(D)$.