Packing Paths in Digraphs
by
Richard Brewster
Capilano College, North Vancouver, B. C., Canada

Let G be a fixed set of digraphs. Given a digraph H, a G-packing in H is a collection P of vertex disjoint subgraphs of H, each isomorphic to a member of G. A G-packing P is maximum if the number of vertices belonging to members of P is maximum, over all G-packings. We focus on the case when G is a family of directed paths. We show that unless G is (essentially) either {[P\vec]₁ }, or { [P\vec]₁, [P\vec]₂ }, the G-packing problem is NP-complete.

When G = { [P\vec]₁ }, the G-packing problem is simply the matching problem. In the one remaining case, G = { [P\vec]₁, [P\vec]₂ }, we give 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 G consisting of all directed paths and cycles.

Date received: May 1, 2001