The real truth about star designs

Determining whether the edges of an input graph G can be partitioned into k-stars is NP-complete. However, with some extra information, we can convert this to a flow problem, giving both a polynomial algorithm, and a strong theoretical tool.