Let G be a graph, and let F a family of subgraphs of G. An edge subset A of G is called an F-packing of G if every component of the subgraph G[A] induced by A in G is a member of F. The F-packing problem consists of finding an F-packing A of G that covers the maximum number of vertices. The F-packing problems have been studied extensively by many authors for different classes of families F. The complexity status of an F-packing problem essentially depends on the family F. The problem turns out to be NP-hard for most families F. Surprisingly, it can be solved in polynomial time for some nontrivial classes of families. For example, the S_n-packing problem (where S_n is the set of stars of G having at most n edges) is a simple generalization of the matching problem that turns out to be polynomial.

Our main goal is to discuss the IS_n-packing problem, namely the problem of packing induced stars of G having at most n edges. We will show that this problem can be solved in polynomial time and that many classical results on matchings (such as the Tutte 1-Factor Theorem, the Berge Duality Theorem, the Gallai-Edmonds Structure Theorem, the Matching Matroid Theorem) can be extended to induced n-star packings in a graph.

If time permits, we will also discuss

<ol> <li> some natural generalizations of the S_n- and IS_n-packing problems,

<li> relations between the duality theorem for IS_n-packing and some variations of the Hall theorem (joint work with Y. Egawa and M. Kaneko), and

<li> some results on the (generally NP-complete) problem of packing 3-vertex paths in a graph for certain classes of graphs (joint work with Hikoe Enomoto, A. Kaneko, and T. Nishimura). </ol>