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). |

Return to the seminar page.

Please send comments about this page to Maurice Rojas at rojas@math.tamu.edu.