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 ∈ V d H ( v ) 2 or more general ℓ ( d H ) , where ℓ : N V → 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 ( n 5.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. sent a simpler reduction of “minconvex factor of prescribed size” to a single minimum weighted f-factor problem resulting in an overall complexity of O ( m 2 log ( n ) ) .