An Edmonds-Gallai-type decomposition for the \(j\)-restricted \(k\)-matching problem (Q2288180)

Let \(G\) be a simple undirected graph, and \(j\) and \(k\) be two integers such that \(j\geq0\) and \(k>0\). A \(k\)-matching of \(G\) is a subgraph \(M\) of \(G\) with no isolated node and degrees at most \(k\). A \(j\)-restricted \(k\)-matching in \(G\) is a \(k\)-matching whose each connected component has more than \(j\) edges. Recently, \textit{Y. Li} [Math. Oper. Res. 39, No. 3, 930--948 (2014; Zbl 1309.90088)] investigated the maximum non-negative node weighted \(j\)-restricted \(k\)-matching problem, presented a polynomial-time algorithm and a min-max theorem for \(0\leq j<k\), and verified the NP-hardness of the problem with unit node weights and \(2\leq k\leq j\). In this article, the authors obtain an Edmonds-Gallai-type decomposition theorem for the \(j\)-restricted \(k\)-matching problem with \(0\leq j<k\), and pose an alternative proof to the min-max theorem of Li [loc. cit.] using the analogous decomposition for \(k\)-piece packings given by \textit{M. Janata} et al. [ Electron. J. Comb. 12, No. 1, Research paper R8, 21 p. (2005; Zbl 1062.05119)]. These results are important and interesting.