*Given a graph G, ï¬nd a packing of induced stars of
restricted size in G having the maximum number of
vertices. *

This problem is a natural generalization of the classical problem of ï¬nding in a graph a maximum matching.

We will show that all main results of matching theory can be extended to this problem. Namely, we will give a polynomial-time algorithm for solving this problem, the duality theorem, and the graph structure theorem (similar to that of Tutte-Berge duality theorem and Edmonds-Gallai structure theorem for matchings).

We will also discuss the matroid theory aspects of the above star packing problem.