A Scaling Algorithm for Weighted $f$-Factors in General Graphs

Abstract

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

35 pages