Generalized star packing problems
Marek Janata, Jácint Szabó · 2004
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.