Sidepath results on packing $\vec{P}_1$'s and $\vec{P}_2$'s

This report provides proofs and refinements of some results from our companion paper [1: Packing paths in digraphs, R.C. Brewster, P. Hell, S.H. Pantel, R. Rizzi, A. Yeo, Journal of Graph Theory 2003]. We refer the reader to [1] for a more detailed introduction to notation, background, and motivation. 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$, not necessarily induced, each isomorphic to a member of $\cal G$. A $\cal G$-packing $\cal P$ is {\em 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. In a companion paper we initiate the study of digraph packing problems, focusing on the case when $\cal G$ is a family of directed paths. We showed that unless $\cal G$ is (essentially) either $\{ \vec{P}_1 \}$, or $\{ \vec{P}_1, \vec{P}_2 \}$, the $\cal G$-packing problem is NP-complete. We use the notation $\vec{P}_k$ for the \emph{directed path of length $k$}, i.e., the path $u_0, u_1, \dots, u_k$ in which all arcs are oriented from $u_{i-1}$ to $u_i$ for $i=1, 2, \dots k$. When ${\cal G} = \{ \vec{P}_1 \}$, the $\cal G$-packing problem is simply the matching problem. In [2: On the complexity of digraph packings, R.C. Brewster, R. Rizzi, IPL 2003], we treat in detail the one remaining case, ${\cal G} = \{ \vec{P}_1, \vec{P}_2 \}$. We give in this case a polynomial time algorithm based on augmenting configurations, and a corresponding Berge-type and Tutte-type theorems. We also give a reduction to bipartite matching. In this report, we give a direct combinatorial algorithm based on augmentations, explore weighted variants of the problem, and give a polyhedral analysis.