The Edmonds-Gallai Decomposition for the $k$-Piece Packing Problem

Abstract

Generalizing Kaneko's long path packing problem, Hartvigsen, Hell and Szabó consider a new type of undirected graph packing problem, called the $k$-piece packing problem. A $k$-piece is a simple, connected graph with highest degree exactly $k$ so in the case $k=1$ we get the classical matching problem. They give a polynomial algorithm, a Tutte-type characterization and a Berge-type minimax formula for the $k$-piece packing problem. However, they leave open the question of an Edmonds-Gallai type decomposition. This paper fills this gap by describing such a decomposition. We also prove that the vertex sets coverable by $k$-piece packings have a certain matroidal structure.