Generalized star packing problems

Marek Janata, Jácint Szabó


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-17}

Last modification: 22.11.2022. Please email your comments to Tamás Király!