Oriented star packings (Q2483479)

Given a family \(S\) of oriented stars, an \(S\)-packing in a digraph \(D\) is a collection of vertex disjoint subgraphs of \(D\), each of which is isomorphic to a member of \(S\). The \(S\)-packing problem is to ascertain the maximum number of vertices of a host \(D\) that can be covered by an \(S\)-packing of \(D\). The paper shows 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 problem, it provides Hall type min-max theorems, including versions for locally degree-constrained variants of the problems. It also shows that the \(S\)-packing problem is polynomial for some \(S\) and NP-complete otherwise.