Let $\cal G$ be a fixed family of directed graphs. A $\cal G$-packing of a digraph $H$ is a collection of vertex-disjoint subgraphs of $H$, each isomorphic to a member of $\cal G$. A $\cal G$-packing problem is a problem to decide if an instance graph $H$ has a $\cal G$-packing that covers at least $k$ vertices of $H$ (where $k$ is a part of the instance). Denote by $\vec{P}_m$ a directed path of length $m$. The authors prove that the $\cal G$-packing problem is NP-complete for a family of directed paths ${\cal G}\subseteq \{\vec{P}_1,\vec{P}_2,\vec{P}_3,\ldots\}$ unless $\cal G$ satisfies one of the conditions: (i) $\vec{P}_1 \in {\cal G}$ and each member of $\cal G$ has an odd length, or (ii) $\vec{P}_1,\vec{P}_2 \in {\cal G}$. \noindent When $\cal G$ satisfies (i) or (ii), the $\cal G$-packing problem is polynomial time solvable. In case (ii) (which is more interesting than case (i)) the authors prove a Berge type augmentation configuration theorem and a min-max characterization. They also construct a polynomial time algorithm solving the $\cal G$-packing problem in this case.
Reviewer: Zbigniew Lonc (Warszawa)