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 S-Packing 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,ℓ)∈N2∖(0,0) denoting the number of out- and in-neighbours of the centre vertex. For p,q,d∈N∪{∞}, we denote by Sp,q,d the family of stars (k,ℓ) such that k⩽p, and ℓ⩽q, and 0