Decompositions of complete multigraphs into stars of varying sizes

In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size m exists whenever some obvious necessary conditions hold. In 1992 Lonc gave necessary and sufficient conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes m₁,…,m_t. We show that the general problem of when a complete multigraph admits a decomposition into stars of sizes m₁,…,m_t is NP-complete, but that it becomes tractable if we place a strong enough upper bound on max⁡(m₁,…,m_t). We determine the upper bound at which this transition occurs. Along the way we also give a characterisation of when an arbitrary multigraph can be decomposed into stars of sizes m₁,…,m_t with specified centres, and a generalisation of Landau's theorem on tournaments.