Oriented star packings

Given a (possibly infinite) family S of oriented stars, an S-packing in a digraph D is a collection of vertex disjoint subgraphs of D, each isomorphic to a member of S. The STACKING problem asks for the maximum number of vertices, of a host digraph D, that can be covered by an S-packing of D. We prove a dichotomy for the decision version of the S-packing problem, giving an exact classification of which problems are polynomial time solvable and which are NP-complete. For the polynomial problems, we provide Hall type min-max theorems, including versions for (locally) degree-constrained variants of the problems. An oriented star can be specified by a pair of (k, l) is an element of N-2 \ (0, 0) denoting the number of out-and in-neighbours of the centre vertex. For p, q, d is an element of N U {infinity}, we denote by S-p,S-q,S-d the family of stars (k, l) such that k <= p, and l <= q, and 0 < k + l <= d. We prove the S-PACKING problem is polynomial if S = S-p,S-q,S-d for some p, q, d is an element of Z(+) U {infinity}, and NP-complete otherwise.