标题： 有向悬挂Steiner树在有向图中的内部不相交性 显示英文标题

标题： Internally-disjoint Directed Pendant Steiner Trees in Digraphs

摘要： 对于一个有向图$D=(V(D),A(D))$和一个具有$|S|\geq 2$和$r\in S$的集合$S\subseteq V(D)$，一个有向悬挂$(S,r)$-Steiner树（或者简单地称为悬挂$(S,r)$-树）是以$r$为根的外向树$T$，满足$S\subseteq V(T)$并且$S$中每个顶点在$T$中度数为一。 两个悬挂的$(S,r)$-树被称为内部不相交，如果它们没有弧的重叠且它们的公共顶点集恰好是$S$。 {\sc 内部不相交有向悬挂Steiner树打包（IDPSTP）}问题的目标是在$D$中找到最大数量的成对内部不相交的悬挂$(S,r)$-树。 我们用$\tau_{S,r}(D)$表示$D$中最大数量的成对内部不相交悬挂$(S,r)$树，并定义$D$的有向悬挂树$k$连通性为 \begin{align*} \tau_{k}(D)=\min\{\tau_{S,r}(D)\mid S\subseteq V(D),|S|=k,r\in S\}. \end{align*} IDPSTP 是由 Cheriyan 和 Salavatipour [Algorithmica, 2006] 以及 Sun 和 Yeo [JGT, 2023] 研究的{\sc 内部不相交的有向Steiner树包装}问题的一个限制。 有向悬挂树$k$-连通性扩展了 Hager 在无向图中研究的悬挂树$k$-连通性的概念，可以被视为对有向图的经典顶点连通性的推广。 本文中，我们完全确定了参数$\tau_{S,r}(D)$在欧拉有向图和对称有向图上的计算复杂度。 我们还给出了参数$\tau_{k}(D)$的精确界值。 显示英文摘要

摘要： For a digraph $D=(V(D),A(D))$ and a set $S\subseteq V(D)$ with $|S|\geq 2$ and $r\in S$, a directed pendant $(S,r)$-Steiner tree (or, simply, a pendant $(S,r)$-tree) is an out-tree $T$ rooted at $r$ such that $S\subseteq V(T)$ and each vertex of $S$ has degree one in $T$. Two pendant $(S,r)$-trees are called internally-disjoint if they are arc-disjoint and their common vertex set is exactly $S$. The goal of the {\sc Internally-disjoint Directed Pendant Steiner Tree Packing (IDPSTP)} problem is to find a largest collection of pairwise internally-disjoint pendant $(S,r)$-trees in $D$. We use $\tau_{S,r}(D)$ to denote the maximum number of pairwise internally-disjoint pendant $(S,r)$-trees in $D$ and define the directed pendant-tree $k$-connectivity of $D$ as \begin{align*} \tau_{k}(D)=\min\{\tau_{S,r}(D)\mid S\subseteq V(D),|S|=k,r\in S\}. \end{align*} IDPSTP is a restriction of the {\sc Internally-disjoint Directed Steiner Tree Packing} problem studied by Cheriyan and Salavatipour [Algorithmica, 2006] and Sun and Yeo [JGT, 2023]. The directed pendant-tree $k$-connectivity extends the concept of pendant-tree $k$-connectivity in undirected graphs studied by Hager [JCTB, 1985] and could be seen as a generalization of classical vertex-connectivity of digraphs. In this paper, we completely determine the computational complexity for the parameter $\tau_{S,r}(D)$ on Eulerian digraphs and symmetric digraphs. We also give sharp bounds and values for the parameter $\tau_{k}(D)$.