Internally-disjoint Pendant Steiner Trees in Digraphs

Abstract

For a digraph $D=(V(D),A(D))$ and a set $S\subseteq V(D)$ with $|S|\ge 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$. Let $\ddot{I}{„}_k(D)=\min \{\ddot{I}{„}_{S,r}(D)\mid S\subseteq V(D),|S|=k,r\in S\}$, where $\ddot{I}{„}_{S,r}(D)$ denotes the maximum number of pairwise internally-disjoint pendant $(S,r)$-trees in $D$. In this paper, we first completely determine the computational complexity for the decision version of IDPSTP on Eulerian digraphs and symmetric digraphs. We then show that, for any $\hat{I}\mu >0$, given an instance of IDPSTP with order $n$, it is NP-hard to approximate the solution within $O(n^{1/3-\hat{I}\mu })$. Finally, we get some sharp bounds for the parameter $\ddot{I}{„}_k(D)$.