|
Title:
On packing subgraphs in a graph
Abstract: Let G be a graph, and 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 extensively been studied by many authors for different classes of families F. Clearly the complexity status of an F-packing problem essentially depends on the family F. It is not surprising that the problem turns out to be NP-hard for most of the families F. Surprisingly the problem can be solved in polynomial time for some non-trivial 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 simplest 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. We will also discuss (if time permits) (1) some natural generalizations of the S_n- and IS_n-packing problems, (2) relations between the duality theorem for IS_n-packing problem and some variations of the Hall theorem (joint work with Y. Egawa and M. Kaneko), and (3) 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). |