An Edmonds-Gallai-Type Decomposition for the j-Restricted k-Matching Problem - Li, Yanjun; Szabó, Jácint (The Electronic Journal of Combinatorics, 2020)
Given a non-negative integer j and a positive integer k, a j-restricted k-matching in a simple undirected graph is a k-matching, so that each of its connected components has at least j+1 edges. The maximum non-negative node weighted j-restricted k-matching problem was recently studied by Li who gave a polynomial-time algorithm and a min-max theorem for 0 j < k, and also proved the NP-hardness of the problem with unit node weights and 2 k j. In this paper we derive an Edmonds–Gallai-type decomposition theorem for the j-restricted k-matching problem with 0 j < k, using the analogous decomposition for k-piece packings given by Janata, Loebl and Szabó, and give an alternative proof to the min-max theorem of Li.