  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_1,\ldots,m_t$. We show that the general problem of when a complete
multigraph admits a decomposition into stars of sizes $m_1,\ldots,m_t$ is
$\mathsf{NP}$-complete, but that it becomes tractable if we place a strong
enough upper bound on $\max(m_1,\ldots,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_1,\ldots,m_t$ with specified centres, and a generalisation of Landau's
theorem on tournaments.
