Packing paths in digraphs

Let be a fixed set of digraphs. Given a digraph H, a -packing in H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . A -packing is maximum if the number of vertices belonging to members of is maximum, over all -packings. The analogous problem for undirected graphs has been extensively studied in the literature. The purpose of this paper is to initiate the study of digraph packing problems. We focus on the case when is a family of directed paths. We show that unless is (essentially) either , or , the G-packing problem is NP-complete. When , the -packing problem is simply the matching problem. We treat in detail the one remaining case, . We give in this case a polynomial algorithm for the packing problem. We also give the following positive results: a Berge type augmenting configuration theorem, a min-max characterization, and a reduction to bipartite matching. These results apply also to packings by the family consisting of all directed paths and cycles. We also explore weighted variants of the problem and include a polyhedral analysis.