Complexity of directed Steiner path packing problem

Yuefang Sun

For a digraph $D=(V(D), A(D))$, and a set $S\subseteq V(D)$ with $r\in S$ and $|S|\geq 2$, a directed $(S, r)$-Steiner path or, simply, an $(S, r)$-path is a directed path $P$ started at $r$ with $S\subseteq V(P)$. Two $(S, r)$-paths are said to be arc-disjoint if they have no common arc. Two arc-disjoint $(S, r)$-paths are said to be internally disjoint if the set of common vertices of them is exactly $S$. Let $\kappa^p_{S,r}(D)$ (resp. $\lambda^p_{S,r}(D)$) be the maximum number of internally disjoint (resp. arc-disjoint) $(S, r)$-paths in $D$. In this paper, we study the complexity for $\kappa^p_{S,r}(D)$ and $\lambda^p_{S,r}(D)$. When both $k\geq 2, \ell\geq 1$ are fixed integers, we show that the problem of deciding whether $\kappa^p_{S,r}(D) \geq \ell$ for an Eulerian digraph $D$ is NP-complete, where $r\in S\subseteq V(D)$ and $|S|=k$. However, when we consider the class of symmetric digraphs, the problem becomes polynomial-time solvable. We also show that the problem of deciding whether $\lambda^p_{S,r}(D) \geq \ell$ for a given digraph $D$ is NP-complete, where $r\in S\subseteq V(D)$ and $|S|=k$.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment