The superstar packing problem

Hell and Kirkpatrick proved that in an undirected graph, a maximum size packing by a set of non-singleton stars can be found in polynomial time if this star-set is of the form {S ₁, S ₂, ..., S _k } for some k∈ℤ₊ (S _i is the star with i leaves), and it is NP-hard otherwise. This may raise the question whether it is possible to enlarge a set of stars not of the form {S ₁, S ₂, ..., S _k } by other non-star graphs to get a polynomially solvable graph packing problem. This paper shows such families of depth 2 trees. We show two approaches to this problem, a polynomial alternating forest algorithm, which implies a Berge-Tutte type min-max theorem, and a reduction to the degree constrained subgraph problem of Lovász. Research is supported by OTKA grants K60802, TS049788 and by European MCRTN Adonet, Contract Grant No. 504438.