Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
How would one find a minimum-weight perfect b-matching of a general graph, where the number of edges incident on each vertex is a positive even number not greater than b?
A minimum-weight perfect b-matching of a graph G is a subgraph M of minimal total edge weight, such that each vertex in G is incident by exactly b edges from M.
A subgraph in which each vertex has degree exactly $b$ is known as a $b$-factor. You are asking for something similar (but not identical) to the minimum weight $b$-factor.
Tutte showed how to reduce minimum weight $b$-factor to minimum weight perfect matching in his paper A short proof of the factor theorem for finite graphs.
We will split each vertex $v$ of degree $d(v)$ into $2d(v) - b$ vertices: $v_1,\ldots,v_{d(v)},v'_1,\ldots,v'_{d(v)-b}$ (we can assume that $d(v) \geq b$, since otherwise the graph has no $b$-factor). We lift each edge $(x,y)$ to an edge $(x_i,y_j)$ of the same weight in such a way that each $x_i$ and $y_j$ participates in exactly one such edge. We furthermore connect each $v_i$ to each $v'_j$ with a zero-weight edge, for all $i \in [d(v)]$ and $j \in [d(v)-b]$.
Each $b$-factor of the original graph corresponds to a matching in the new graph of the same weight. Indeed, lift the $b$-factor to the new graph, and for each vertex $v$, add an arbitrary matching between $v'_1,\ldots,v'_{d(v)-b}$ and the $d(v)-b$ new vertices corresponding to "unused ports".
Conversely, we can convert every matching in the new graph to a $b$-factor of the same weight in the original graph by undoing this construction.
