Minconvex graph factors of prescribed size and a simpler reduction to weighted f-factors

Recently, András Sebő and Nicola Apollonio considered the following generalization of the problem to determine a matching of size k. Given a graph G=(V,E) and an integer k, determine a subgraph H=(V,F) of G that minimizes ∑v∈VdH2(v) or more general ℓ(dH), where ℓ:NV→R is a separable convex function, and |F|=k. They proved, that the problem is polynomially solvable in two ways. First, it admits “augmenting pairs of alternating paths” which, according to their analysis, yields a complexity of O(n5.5), if ℓ is a quadratic convex function. On the other hand they reduced the problem to a single minimum weight f-factor problem. Their reduction introduces quite a few new vertices and edges such that the resulting complexity is higher.We present a simpler reduction of “minconvex factor of prescribed size” to a single minimum weighted f-factor problem resulting in an overall complexity of O(m2log(n)).