A Scaling Algorithm for Weighted f-Factors in General Graphs

We study the maximum weight perfect f-factor problem on any general simple graph G = (V,E,?) with positive integral edge weights w, and n = |V|, m = |E|. When we have a function f:V ? ?_+ on vertices, a perfect f-factor is a generalized matching so that every vertex u is matched to exactly f(u) different edges. The previous best results on this problem have running time O(m f(V)) [Gabow 2018] or O?(W(f(V))^2.373)) [Gabow and Sankowski 2013], where W is the maximum edge weight, and f(V) = ?_{u ? V}f(u). In this paper, we present a scaling algorithm for this problem with running time O?(mn^{2/3} log W). Previously this bound is only known for bipartite graphs [Gabow and Tarjan 1989]. The advantage is that the running time is independent of f(V), and consequently it breaks the ?(mn) barrier for large f(V) even for the unweighted f-factor problem in general graphs