Directed Steiner path packing and directed path connectivity
share
For a digraph D=(V(D), A(D)), and a set S⊆ V(D) with r∈ S and |S|≥ 2, a directed (S, r)-Steiner path or, simply, an (S, r)-path is a directed path P started at r with S⊆ 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 κ^p_S,r(D) (resp. λ^p_S,r(D)) be the maximum number of internally disjoint (resp. arc-disjoint) (S, r)-paths in D. The directed path k-connectivity of D is defined as κ^p_k(D)= min{κ^p_S,r(D)| S⊆ V(D), |S|=k, r∈ S}. Similarly, the directed path k-arc-connectivity of D is defined as λ^p_k(D)= min{λ^p_S,r(D)| S⊆ V(D), |S|=k, r∈ S}. The directed path k-connectivity and directed path k-arc-connectivity are also called directed path connectivity which extends the path connectivity on undirected graphs to directed graphs and could be seen as a generalization of classical connectivity of digraphs. In this paper, we obtain complexity results for κ^p_S,r(D) on Eulerian digraphs and symmetric digraphs, and λ^p_S,r(D) on general digraphs. We also give bounds for the parameters κ^p_k(D) and λ^p_k(D).
READ FULL TEXT