Kernels for packing and covering problems

We show how the notion of combinatorial duality, related to the well-known notion of duality from linear programming, may be used for translating kernel results obtained for packing problems into kernel results for covering problems. We exemplify this approach by having a closer look at the problems of packing a graph with vertex-disjoint trees or vertex-disjoint stars with r edges. The case r = 2 has been studied in several other papers. By establishing a general notion of a crown, we show how linear-size vertex kernels can be efficiently achieved for the mentioned problems.

Authors

• Jianer Chen
• Henning Fernau
• Peter Shaw
• Jianxin Wang
• Zhibiao Yang

Keywords

• Combinatorial problems
• Packings
• Coverings
• Kernelization
• Crown decomposition