ALGORITHMS FOR WEIGHTED MATCHING GENERALIZATIONS I: BIPARTITE GRAPHS, b-MATCHING, AND UNWEIGHTED f-FACTORS

Let G = (V;E) be a weighted graph or multigraph, with f or b a function assigning a nonnegative integer to each vertex. An f-factor is a subgraph whose degree function is f; a perfect b-matching is a b-factor in the graph formed from G by adding an unlimited number of copies of each edge. This two-part paper culminates in an efficient algebraic algorithm to find a maximum f-factor, i.e., f -factor with maximum weight. Along the way it presents simpler special cases of interest. Part II presents the maximum f -factor algorithm and the special case of shortest paths in conservative undirected graphs (negative edges allowed). Part I presents these results: An algebraic algorithm for maximum b-matching, i.e., maximum weight b-matching. It is almost identical to its special case b 1, ordinary weighted matching. The time is O (Wb(V)!) for W the maximum magnitude of an edge weight, b(V) = P v2V b(v), and ! < 2:373 the exponent of matrix multiplication. An algebraic algorithm to find an f-factor. The time is O(f (V)!) for f (V) = P v2V f (v). The specialization of the f -factor algorithm to bipartite graphs and its extension to maximum/minimum bipartite f factors. This improves the known complexity bounds for vertex capacitated max-flow and min-cost max-flow on a subclass of graphs. Each algorithm is randomized and has two versions achieving the above time bound: For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas.