Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths

For an undirected graph or multigraph $G=(V,E)$ and a function $f:V\to \mathbb{Z_+}$, an $f$-factor is a subgraph whose degree function is $f$. For integral edge weights of maximum magnitude $W$ our algorithm finds a maximum weight $f$-factor in time $\tilde{O}(Wf(V)^{\omega})$, where $f(V)=\sum_{v\in V} f(v)$ and $\omega$ is the exponent of matrix multiplication. The algorithm is randomized and has two versions. For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas. The algorithm is based on a detailed analysis of the structure of the optimum blossoms. A special case gives a representation for single-source shortest-paths in conservative undirected graphs, generalizing the standard shortest-path tree to a “tree of cycles”. The representation can be constructed by a randomized algorithm with the same time bound as above, or deterministically by an algorithm for maximum weight matching, achieving time $O(n(m + n \log n))$ or $O(\sqrt{n }\ m \log (nW))$