|
|
|
Results of Las Vergnas, Hell and Kirkpatrick imply that packing an undirected graph by a set of stars is polynomial if and only if this set is of type {S1,S2,...,Sk}. That is, forbidding some stars from this `sequential' set gives an NP-complete problem. This arises the question if it is possible to recover polynomiality by allowing some other non-star graphs to be components of the packing. This paper shows two types of graph sets which can be added to a non-sequential set of stars to maintain polynomiality. These new graphs are trees constructed from a star by replacing some of its leaves by forbidden stars of the packing. For both of these packing problems we show Edmonds-type algorithms implying Berge-type theorems, and the matroidality of the packings. In one of the Edmonds-type algorithms the alternating forest may overlap itself. We use reductions to the H-factor problem of Lovász.
Bibtex entry:
| AUTHOR | = | {Janata, Marek and Szab{\'o}, J{\'a}cint}, |
| TITLE | = | {Generalized star packing problems}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2004}, |
| NUMBER | = | {TR-2004-17} |