Abstract
Let ${\cal G}$ be a fixed set of digraphs. Given a digraph H, a ${\cal G}$βpacking in H is a collection ${\cal P}$ of vertex disjoint subgraphs of H, each isomorphic to a member of ${\cal G}$. A ${\cal G}$βpacking ${\cal P}$ is maximum if the number of vertices belonging to members of ${\cal P}$ is maximum, over all ${\cal G}$β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 ${\cal G}$ is a family of directed paths. We show that unless ${\cal G}$ is (essentially) either ${ \vec {P}_1 }$, or ${ \vec {P}_1, \vec {P}_2 }$, the Gβpacking problem is NPβcomplete. When ${\cal G} = { \vec {P}_1 }$, the ${\cal G}$βpacking problem is simply the matching problem. We treat in detail the one remaining case, ${\cal G} = { \vec {P}_1, \vec {P}_2 }$. 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 ${\cal G}$ consisting of all directed paths and cycles. We also explore weighted variants of the problem and include a polyhedral analysis. Β© 2003 Wiley Periodicals, Inc. J Graph Theory 44: 81β94, 2003